山坡上有一条路，从山顶一直延伸到山脚。沿路种植着 $n$ 棵老树。当地政府决定砍伐这些树木。为了不浪费木材，每棵树都应该被运送到锯木厂。

树木只能朝一个方向运输：向下（向山脚方向）。在路的尽头（山脚）已经建有一座锯木厂。此外，还可以在沿路的其他位置新建两座锯木厂。你需要决定这两座新锯木厂建在什么位置，以使总运输成本最小。每公斤木材每运输一米需要花费 $1$ 分钱。

任务

编写一个程序：

• 从标准输入读取树木的数量、它们的重量和位置；
• 计算最小的总运输成本；
• 将结果输出到标准输出。

输入格式

输入的第一行包含一个整数 $n$ — 树木的数量（$2 \le n \le 20\,000$）。树木从山顶到山脚依次编号为 $1, 2, \dots, n$。

接下来的 $n$ 行，每行包含两个由单个空格分隔的正整数。第 $i+1$ 行包含：$w_i$ — 第 $i$ 棵树的重量（单位：公斤），以及 $d_i$ — 第 $i$ 棵树与第 $i+1$ 棵树之间的距离（单位：米），其中 $1 \le w_i \le 10\,000$，$0 \le d_i \le 10\,000$。最后一个数字 $d_n$ 表示第 $n$ 棵树到山脚锯木厂的距离。

保证将所有树木运送到山脚锯木厂的总成本小于 $2\,000\,000\,000$ 分。

输出格式

输出的第一行且仅有一行，包含一个整数：最小的总运输成本。

样例

输入样例 1

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

输出样例 1

26

说明

下图展示了样例数据中锯木厂的最佳建设位置。树木用圆圈表示，圆圈下方的数字为其重量。锯木厂用黑色圆圈表示。

总成本计算如下：

$$1 \cdot (2 + 1) + 2 \cdot 1 + 1 \cdot (1 + 2) + 3 \cdot 2 + 2 \cdot (1 + 2 + 1) + 1 \cdot (2 + 1) + 1 \cdot 1$$