题目描述

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$