Selling bamboo trees

You have one bamboo tree. It grows at different speeds on different days. You’d like to earn some money by cutting and selling it (the tree still continue growing after you cut them).
The bamboo has a length of 0 on day 1 and grows for n days. You’re aware of how much each meter of bamboo costs on each of the days and how much it grows the night before selling.
notion image
For each day you can either cut the whole tree (it still continues to grow after cutting) and sell it or you can leave it to grow further. What is the maximum amount of money you can earn?

Input

The first line of the input contains a single integer n (1 ≤ n ≤ ) the number of days.
The next n lines contain two space-separated integers (, ) (1 ≤ , ) the number of meters the tree will grow the night before selling and the price for 1 meter of bamboo on the day i.

Output

The program should print the maximum amount you can earn by growing and selling the bamboo. It’s guaranteed that the answer does not exceed .

Examples

Input
Output
8 7 2 1 4 3 3 5 5 4 2 2 5 7 4 1 1
139
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue