题目描述

FJ 把贝蒂带到农场的一块平地上，那里已经有 \(n\) 头奶牛排成一行等着他们了。每头奶牛手上拿着一张正反两面都写着数字的纸。平地上还画着 \(n\) 个方框，有一半方框前面是正号，另一半方框前面是负号，负号和正号间隔出现，例如当 \(n=10\) 时，如下所示：

\(-□+□-□+□-□+□-□+□-□+□\)

贝蒂只能从每张纸上各选择一个数字，然后将选择好的数字那一面向上，再把纸张贴在方框里。然后计算这个表达式的值。

现在贝蒂想知道，这个表达式的最小值是多少。

格式

输入格式

输入第 \(1\) 行一个整数 \(n\)。

接下来输入 \(n\) 行，每行 \(2\) 个整数 \(a\) 和 \(b\)，表示每张纸的正面和反面数字。

输出格式

输出一行一个整数，表示表达式的最小值。

样例1

样例输入1

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

样例输出1

-34

样例解释

框的格式为：\(-□+□-□+□-□+□\)

第一个框将最后一张纸上的 \(4\) 填入；第二个框将第 \(1\) 张纸上的 \(-8\) 填入；

第三个框将第 \(5\) 张纸上的 \(7\) 填入；第四个框将第 \(3\) 张纸上的 \(-3\) 填入；

第五个框将第 \(2\) 张纸上的 \(5\) 填入；第六个框将第 \(4\) 张卡牌的 \(-7\) 填入。

此时表达式的结果为 \(-34\)，是所有可能选择方案中最小的值。

限制

对于 \(30\%\) 的数据，满足 \(n≤8\) 。

对于 \(100\%\) 的数据，满足 \(n≤5×10^5\) 且保证 \(n\) 是偶数，\(|a|,|b|≤10^7\)

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T4\)