配点 : 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