题目描述
查理获得了一家运输公司的定期航线。为了赢利,他必须尽可能地降低成本。他的公司有N(N是偶数)个飞行员组成N/2个机组,每个机组包括两个飞行员——机长和他的助手,机长必须比他的助手年长。每个飞行员有两个可能的工资合同——作为机长或作为助手。同一个飞行员当机长的工资要高于当助手的工资,然而就同一个机组而言,一个助手的工资可能高于他的机长。
编程帮助查理计算将飞行员按最佳组合编组后,所需支付给飞行员的最少工资总额。
输入格式
第1行1个偶数N,表示查理公司所用的飞行员数量。
接下来的N行,包含每个飞行员的工资,按飞行员的年龄由小到大进行排序。每行包含两个整数X和Y,由一个空格隔开,1≤Y<X≤100000,表示该飞行员当机长的工资,Y表示当助手的工资。
输出格式
一行一个数,表示查理所需支付给飞行员的最少工资总额。
样例数据
input
6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000
output
33000
数据规模与约定
2≤N≤10000
时间限制:$3 \text{s}$
空间限制:$64 \text{MB}$