分数: 1000 点
问题陈述
收到 Snuke N 间隔作为生日礼物。 的 i第一个间隔是 [-L_i, R_i]。 可以保证两者 L_i 和 R_i 为阳性。 换句话说,原点严格位于每个区间内。
Snuke 不喜欢重叠的音程,因此他决定移动一些音程。 对于任意正整数 d,如果他支付 d 美元,他可以选择一个间隔并将其移动的距离 d。 也就是说,如果所选段是 [a, b],他可以将其更改为 [a+d, b+d] or [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] to [6, 15] 与 8 美元
- 移动间隔 [-2, 5] to [-1, 6] 与 1 美元
- 移动间隔 [-4, 1] to [-6, -1] 与 2 美元
- 移动间隔 [-7, 5] to [-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