← 返回题目列表

AtCoder · cf16_exhibition_final_f

F. 间隔

中文机器翻译题面 查看原题

分数: 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