SAWMILL - Two Swamills

There are n old trees planted along a road that goes from the top of a hill to its bottom. Local government decided to cut them down. In order not to waste wood each tree should be transported to a sawmill.

Trees can be transported only in one direction: downwards. There is a sawmill at the lower end of the road. Two additional sawmills can be built along the road. You have to decide where to build them, as to minimize the cost of transportation. The transportation costs one cent per meter, per kilogram of wood.

Input

The first line of the input contains one integer n - the number of trees (2 ≤ n ≤ 20,000). The trees are numbered 1, 2, ..., n, starting from the top of the hill and going downwards. Each of the following n lines contains two positive integers separated by single space. Line i + 1 contains: wi - weight (in kilograms) of the i-th tree and di - distance (in meters) between trees number i and i + 1, 1 ≤ wi ≤ 10,000, 1 ≤ di ≤ 10,000. The last of these numbers, dn, is the distance from the tree number n to the lower end of the road. It is guaranteed that the total cost of transporting all trees to the sawmill at the end of the road is less than 2,000,000,000 cents.

Output

The first and only line of output should contain one integer: the minimum cost of transportation.

Example

Input:
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

Output:
26

Added by:acheron
Date:2014-01-04
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CEOI 2004

hide comments
2020-02-13 10:37:40
a problem in CEOI 2004 -> use divide and conquer strategy
good luck (^_^)
2018-11-05 11:53:24
Constraints?
2016-09-02 19:38:09
Nice Problem.
2014-02-15 13:25:05 owt
guys who have solved it help me please. Could you suggest any hint or algorithm, because I am so desperate in solving this :D

Last edit: 2014-03-19 13:25:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.