题目描述

Snuke 收到了 $N$ 个区间作为生日礼物。第 $i$ 个区间是 \[-L_i, R_i\]。保证 $L_i$ 和 $R_i$ 都是正数。换句话说，原点严格地在每个区间内。

Snuke 不喜欢重叠的区间，所以他决定移动一些区间。对于任意正整数 $d$，如果他支付 $d$ 美元，就可以选择一个区间，并将其移动 $d$ 的距离。也就是说，如果选定的区段是 \[a, b\]，他可以将其改为 \[a+d, b+d\] 或 \[a-d, b-d\]。

他可以重复执行这种操作任意次数。操作结束后，区间必须两两不重叠（但可能在某一点上相交）。具体来说，对于任意两个区间，它们的交集长度必须为零。

计算实现他的目标所需的最小成本。

约束条件

• $1 ≤ N ≤ 5000$
• $1 ≤ L_i, R_i ≤ 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $L_1$ $R_1$ : $L_N$ $R_N$

输出

输出实现他的目标所需的最小成本。

输入示例1

4
2 7
2 5
4 1
7 5

输出示例1

22

一种最优解如下：

• 将区间 \[-2, 7\] 移到 \[6, 15\]，花费 $8$ 美元
• 将区间 \[-2, 5\] 移到 \[-1, 6\]，花费 $1$ 美元
• 将区间 \[-4, 1\] 移到 \[-6, -1\]，花费 $2$ 美元
• 将区间 \[-7, 5\] 移到 \[-18, -6\]，花费 $11$ 美元

总成本为 $8 + 1 + 2 + 11 = 22$ 美元。

输入示例2

20
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80
57 18
34 28
76 55
21 80

输出示例2

7337