有一次,Nth在他的抽屉里发现一些空卡片,每张卡片上是些随机数字,把卡片上的数字按照一定的顺序任意填入下面表达式:
每组有两张卡片,可以任意选择其中一个数,组的顺序也可以任意选择,要求填入以上表达式后取得的值最小。过了一会儿Nth想出了一个解决方案。你能做到这一点?
写一个程序来解决上述难题。
第一行包含一个整数n(2 \le n \le 100,000, n是偶数)。
以下n行每行包含两个整数:A_i,B_i(-2,000 \le A_i,B_i \le 2,000, i=1..n)。表示第i组两张卡片的不同数值。
仅一行包含一个整数,表示填入以上表达式后取得的值最小。
6 -8 12 0 5 7 -3 10 -7 -2 7 1 4
-34
选择第1组的-8,第2组的5,第3组的-3,第5组的7,第4组的-7,第6组的4,组成最小表达式的值-34。 (-8)-5+(-3)-7+(-7)-4=-34
10 70 70 62 73 81 65 59 77 99 40 35 88 80 57 76 67 85 57 53 96
-155
选择第2组的62,第1组的70,第4组的59,第3组的81,第5组的40,第8组的76,第6组的35,第9组的85,第7组的57,第10组的96,组成最小表达式的值-155。 62-70+59-81+40–76+35–85+57-96=-155