The dwellers of the island Abstinence are very fond of alkoholfree beer. Hitherto alkohol-free beer was imported from Poland, but this year one of the cities on Abstinence is going to build a brewery. All the cities of this island lie on the coast and are connected by a highway running around the island along its shore. The investor building the brewery collected information about the demand for beer, i.e. how many tanks of beer are needed daily in each city. He has also a table of distances between cities. The cost of transporting one tank is 1 thaler per mile. A daily cost of transport is the amount of money, which has to be spent on transporting a necessary number of tanks of beer from the brewery to each city. The daily cost depends on the location of the brewery. The investor wants to find a location that minimizes the daily cost.

Task

Write a program which

• reads the number of cities, distances between them and daily requests for beer from the text file BRO.IN,
• computes the minimal daily cost of transport,
• writes the result to the text file BRO.OUT.

Input

In the first line of the text file BRO.IN there is one integer n - the number of cities, 5 <= n <= 10 000. (We assume that cities are numbered along the highway, so that the neighbouring cities have subsequent numbers. Cities 1 and n are neighbours too.) In each of the following n lines there are two non-negative numbers separated by a single space. Numbers z_i d_i written in the line (i+1) are respectively the demand for beer in the city i and the distance (in miles) from city i to the next city on the highway. The entire length of the highway is not greater than 1 000 000 miles. The demand for beer in each city is not greater than 1 000 tanks.

Output

Your program should write in the first and only line of the text file BRO.OUT exactly one integer equal to the minimal daily cost of transport.

Example

For the input file BRO.IN:

6
1 2
2 3
1 2
5 2
1 10
2 3

The correct answer is the output file BRO.OUT:

41