CF38E.Let's Go Rolling!

On a number axis directed from the left rightwards, n marbles with coordinates _x_1, _x_2, ..., x__n are situated. Let's assume that the sizes of the marbles are infinitely small, that is in this task each of them is assumed to be a material point. You can stick pins in some of them and the cost of sticking in the marble number i is equal to c__i, number c__i may be negative. After you choose and stick the pins you need, the marbles will start to roll left according to the rule: if a marble has a pin stuck in it, then the marble doesn't move, otherwise the marble rolls all the way up to the next marble which has a pin stuck in it and stops moving there. If there is no pinned marble on the left to the given unpinned one, it is concluded that the marble rolls to the left to infinity and you will pay an infinitely large fine for it. If no marble rolled infinitely to the left, then the fine will consist of two summands:

• the sum of the costs of stuck pins;
• the sum of the lengths of the paths of each of the marbles, that is the sum of absolute values of differences between their initial and final positions.

Your task is to choose and pin some marbles in the way that will make the fine for you to pay as little as possible.

在一条从左向右延伸的数轴上，分布着 $ n $ 个坐标分别为 $ x_1, x_2, \dots, x_n $ 的弹珠。假设弹珠的尺寸无限小，即本题中每个弹珠均视为一个质点。你可以在其中一部分弹珠上插入图钉，插入第 $ i $ 个弹珠的代价为 $ c_i $，其中 $ c_i $ 可能为负数。在你选定并插入图钉后，所有弹珠将按如下规则向左滚动：若某弹珠上插有图钉，则它保持静止；否则，该弹珠将一直向左滚动，直至碰到左侧第一个插有图钉的弹珠，并停在那里。若某个未插图钉的弹珠左侧不存在任何插有图钉的弹珠，则认为该弹珠向左滚动至无穷远处，此时你将为此支付无穷大的罚金。

若没有任何弹珠向左滚动至无穷远处，则你的总罚金由以下两部分构成：

• 所有已插入图钉的代价之和；
• 每个弹珠滚动路径长度之和，即每个弹珠初始位置与最终位置之差的绝对值之和。

你的任务是选择并插入若干图钉，使得你所需支付的罚金最小。

The first input line contains an integer n (1 ≤ n ≤ 3000) which is the number of marbles. The next n lines contain the descriptions of the marbles in pairs of integers x__i, c__i ( - 109 ≤ x__i, c__i ≤ 109). The numbers are space-separated. Each description is given on a separate line. No two marbles have identical initial positions.

第一行输入包含一个整数 $n$（$1 \leq n \leq 3000$），表示弹珠的数量。接下来的 $n$ 行每行包含一对整数 $x_i$、$c_i$（$-10^9 \leq x_i, c_i \leq 10^9$），以空格分隔，用于描述第 $i$ 个弹珠。每对描述独占一行。任意两个弹珠的初始位置均不相同。

Output the single number — the least fine you will have to pay.

输出唯一的数字——你需要支付的最少罚款金额。