#6812. [SeqOI 21W] Sequecen

内存限制:128 MiB 时间限制:500 ms 输入文件:cards.in 输出文件:cards.out
题目类型:传统 评测方式:无测试数据
上传者: Ericnth

题目描述

有一次,Nth在他的抽屉里发现一些空卡片,每张卡片上是些随机数字,把卡片上的数字按照一定的顺序任意填入下面表达式:

http://p.hywiki.xyz/2021/11/20/b5746c432b3b6.png

每组有两张卡片,可以任意选择其中一个数,组的顺序也可以任意选择,要求填入以上表达式后取得的值最小。过了一会儿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组两张卡片的不同数值。

输出格式

仅一行包含一个整数,表示填入以上表达式后取得的值最小。

样例

样例1

Cards1.in

6
-8 12
0 5
7 -3
10 -7
-2 7
1 4

Cards1.out

-34

解释

选择第1组的-8,第2组的5,第3组的-3,第5组的7,第4组的-7,第6组的4,组成最小表达式的值-34。
(-8)-5+(-3)-7+(-7)-4=-34

样例2

Cards2.in

10
70 70
62 73
81 65
59 77
99 40
35 88
80 57
76 67
85 57
53 96

Cards2.out

-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