在从左向右的数轴上,放置了 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