Description

Along a straight line from the mountain top to the foot, there are $n$ old trees. The locals have decided to cut them down. To avoid wasting any wood, once a tree is felled, the wood must be transported to a sawmill.

Lumber can only be transported downhill. There is one sawmill at the foot of the mountain. Two additional sawmills will be newly built along the mountain road. You must decide where to build these two sawmills so that the total transportation cost is minimized. Assume it costs one cent to transport $1$ kilogram by $1$ meter.

Your task is to write a program that reads the number of trees and their weights and positions from the input, and computes the minimal transportation cost.

Input Format

The first line contains a positive integer $n$ — the number of trees ($2 \le n \le 20000$). Trees are numbered $1, 2, \dots, n$ from the mountain top down to the foot.

Each of the next $n$ lines contains two integers separated by a space.

The $(i+1)$-th line contains $w_i$ — the weight of the $i$-th tree (in kilograms), and $d_i$ — the distance between the $i$-th and the $(i+1)$-th tree, with $1 \le w_i \le 10000$, $0 \le d_i \le 10000$.

For the last tree, $d_n$ denotes the distance from tree $n$ to the sawmill at the foot of the mountain. It is guaranteed that the total cost of transporting all trees to the sawmill at the foot of the mountain is less than $2 \times 10^9$ cents.

Output Format

Output the minimal transportation cost.

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

26

Hint

The sample illustration; black dots represent sawmills.

Constraints:

• Test points $1$–$5$: $n \le 200$.
• Test points $6$–$7$: $n \le 1000$.
• Test points $7$–$13$: $2 \le n \le 20000$.

Translated by ChatGPT 5