← 返回题目列表

Codeforces · 38/E

E. 让我们滚吧!

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

在从左向右的数轴上,放置了 n 个坐标为 x1、x2、...、xn 的弹珠。让我们假设弹珠的尺寸无限小,也就是说,在这个任务中,每个弹珠都被假设为一个质点。你可以在其中一些弹珠上扎针,粘在弹珠上的成本 i 等于 ci,数 ci 可能是负数。选择并粘上所需的别针后,弹珠将开始按照规则向左滚动:如果弹珠中卡有别针,则弹珠不会移动,否则弹珠会一直滚动到下一个有别针的弹珠并在那里停止移动。如果在给定的未钉住的弹珠的左侧没有钉住的弹珠,则得出结论,弹珠向左滚动到无限远,并且您将为此支付无限大的罚款。如果没有弹珠无限向左滚动,则罚款将包括两个被加数:

- 卡住引脚的成本总和;
- 每个弹珠的路径长度之和,即它们的初始位置和最终位置之间的差的绝对值之和。

你的任务是选择并固定一些弹珠,以使你支付尽可能少的罚款。

输入

第一输入行包含一个整数 n (1 ≤ n ≤ 3000),它是弹珠的数量。接下来的 n 行包含对整数 xi、ci (- 109 ≤ xi, ci ≤ 109) 对中的弹珠的描述。数字以空格分隔。每个描述都在单独的行中给出。没有两个弹珠具有相同的初始位置。

输出

输出单个数字——您需要支付的最少罚款。

示例

输入 #1

3
2 3
3 4
1 2

输出 #1

5

输入 #2

4
1 7
3 1
5 10
6 1

输出 #2

11