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.
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