Two Sawmills

$n$ old trees stand along a road that runs from the top of a hill down to its foot. All of them will be cut down, and to avoid wasting wood every felled tree must be carried to a sawmill.

Wood can be moved in one direction only: downhill. There is already a sawmill at the lower end of the road. You may build two more sawmills at points along the road, and you must choose their locations so that the total transportation cost is as small as possible. Each felled tree travels downhill to the first sawmill at or below its own position. Transportation costs one cent per kilogram of wood per meter.

Given the number of trees together with their weights and positions on the standard input, write a program that computes the minimum possible total transportation cost and prints it to the standard output.

The first line contains the number of trees $n$ ($2 \le n \le 20000$). The trees are numbered $1, 2, \dots, n$ from the top of the hill downwards. Each of the next $n$ lines contains two integers separated by a single space. Line $i$ contains $w_i$, the weight in kilograms of tree $i$ ($1 \le w_i \le 10000$), and $d_i$, the distance in meters between tree $i$ and tree $i+1$ ($0 \le d_i \le 10000$). The last of these distances, $d_n$, is the distance from tree $n$ to the sawmill at the lower end of the road. It is guaranteed that the total cost of carrying every tree to the sawmill at the end of the road is less than 2,000,000,000 cents.

Print a single integer: the minimum total transportation cost.

The two extra sawmills may be placed at tree positions. Every tree is carried to the nearest sawmill at or below its own position. The figure below shows an optimal placement of the sawmills for the first test case; trees are drawn as circles labeled with their weights, and sawmills are marked in black. The resulting minimum cost is

$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 = 26.$