#P1362. [Baltic2005]Cards

[Baltic2005]Cards

题目描述

Adam 在抽屉时发现了一些卡片,他在卡片的正反面随机写了一些数字,然后按其随机排放。

把全部卡片按任意次序放入表达式 x1−x2+x3−x4+⋯+xn−1−xnx_1-x_2+x_3-x_4+\cdots+x_{n-1}-x_n,其中 xix_i 是第 ii 张卡片朝上的数字。求表达式的最小值。

注意 Adam 可以把卡片翻转过来。

输入格式

第一行输入数字 nn 。

下面 nn 行每行两个数字 ai,bia_i,b_i,表示 Adam 写在卡片上的数字。

输出格式

输出表达式的最小值。

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

数据规模与约定

对于 100%100\% 的数据,nn 为偶数,2≤n≤1052\leq n\leq 10^5,∣ai∣,∣bi∣≤2×103|a_i|,|b_i|\leq 2\times 10^3。