G - Good Inflation

The competition is drawing to a close, and The Team could really use another balloon to help them come out on top… good thing they're no chumps, and thought of this in advance! Before the contest started, they instructed an accomplice to go to the local balloon shop, buy an extra balloon, and deliver it to them at the conclusion of the event. It is true that their balloons then won't match up with the scoreboard's record of which problems they've solved - but, in the end, it's the balloons that count! In fact, The Team knows that, the larger their extra balloon, the more their opponents (and the judges) will be intimidated. They're not the best ACM-ICPC team in the world for nothing!

However, this balloon shop is rather strange. The accomplice is given an empty balloon (a balloon with size 0), and told that he can tie it closed and keep it after exactly N (1 ≤ N ≤ 10⁶) minutes. In the meantime, during each minute, an inflation offer is available. If offer i is taken, then, at the start of the i-th minute, the balloon's size will be increased by a_i (0 ≤ a_i ≤ 10⁶). However, since the balloon cannot be closed until the end, its air will leak out at a constant rate, which depends on the gas that was used - in particular, its size will immediately start to decrease at a rate of d_i (0 ≤ d_i ≤ 10⁶) per minute, until either another offer is taken, or the balloon deflates completely (its size can never become negative, of course).

The Team will not be happy if they don't receive the largest balloon possible. Unfortunately, their accomplice happens to be...you. Can you figure out the maximal size that the balloon can have at the start of minute N + 1, before it's too late?

Input

First line: 1 integer, N
Next N lines: 2 integers, a_i and d_i, for i = 1..N

Output

1 integer, the maximal size which the balloon can have at the start of minute N + 1.

Sample Input

5
2 3
10 2
0 1
5 4
1 10

Sample Output

5

Explanation of Sample

The best option is to take only the offers at minutes 2 and 3. At the start of minute 2, the balloon will be inflated to size 10, and will deflate to size 8 by the start of minute 3. At that point, the balloon's size will not change, but its deflation rate will change to 1. As a result, by the start of minute 6, its size will be 5.

Note that, if the offer at minute 1 is additionally taken, the balloon will simply be inflated to size 2 before deflating back to size 0 by the start of minute 2 - therefore, this will not change the outcome.

Also note that, if the offer at minute 4 is additionally taken, the balloon will inflate to size 12 at the start of minute 4, but its deflation rate of 4 will result in a size of 4 at the start of minute 6, which is not optimal.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 4.00s
Memory Limit: 64M
Added: Jun 01, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)