GOODG  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 ACMICPC 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 \leq N \leq 10^6$) 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 \leq a_i \leq 10^6$). 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 \leq d_i \leq 10^6$) 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$.
Example
Input:
5 2 3 10 2 0 1 5 4 1 10
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.
hide comments
Sigma Kappa:
20170720 05:37:10
The convex hull trick here needs to be fully dynamic. STL set<> is your friend, along with custom comparators. Last edit: 20170722 13:19:06 

tomcilo:
20170403 22:43:29
What a great way to solve your 15th problem :D 

Rishav Goyal:
20150822 16:17:49
jacob can you tell me the error in implementation? i am sure i have correct algo. 

ppppppxx:
20150822 16:14:36
Last edit: 20150822 16:14:49 

Alex Abbas:
20140927 15:12:27
@Jacob Plachta could you please see my 12471836 submission, I'm pretty sure it shouldn't give wrong answers...


Dionysis Zindros:
20130803 21:01:25
@Jacob Plachta Could we perhaps have some nontrivial larger testcases to work with? It would help with debugging. See submission id: 9775390 

Giorgos Christoglou:
20130526 09:15:29
@Jacob Plachta could you see please my last submission is anything wrong with my solution logic or just a bug that I should fix? the id: 9346240

Added by:  SourSpinach 
Date:  20130509 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 