← 返回题目列表

AtCoder · relay2018_j

J. 健康诊断

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

配点 : 100 点

問題文

狼和狐狸计划接受体检。健康检查 N 发生在一段时间内,每只狼和狐狸N 几天之内 1 我计划在第二天参加体检。 i 想要参加当天健康检查的狼 w_i 匹、i 想要参加当天健康检查的狐狸 f_i 有。

但是,N 每天只能诊断出一只狼或狐狸。 如果您的愿望不符,您将被要求改天参加。i 想要参加当天健康检查的狼或狐狸 j 当日进行健康检查时,不满意程度为 |i-j| 。 如果没有可以进行健康检查的日子,不满意的程度是 10^{100} 。每只狼和狐狸都会在最不满意的一天参加健康检查。

N 在最优确定每天诊断狼还是狐狸时,找到所有狼和狐狸的总不满意程度的最小值。

制約

  • 2 ≤ N ≤ 3000
  • 0 ≤ w_i, f_i ≤ 10^9

入力

输入是按以下格式从标准输入给出的。

N
w_1 f_1
:
w_N f_N

出力

输出所有狼和狐狸的总不满意程度的最小值。


入力例 1

6
1 5
1 3
3 4
3 2
5 1
6 2

出力例 1

15

3,5,6 当日诊断狼;1,2,4 最好在第一天就诊断你的狐狸。


入力例 2

10
26 37
1 49
1 74
2 99
2 100
2 75
3 62
3 62
2 37
2 37

出力例 2

108