Convention II#10397
Despite long delays in airport pickups, Farmer John's convention for cows interested in eating grass has been going well so far. It has attracted cows from all over the world.
The main event of the convention, however, looks as if it might cause Farmer John further scheduling woes. A very small pasture on his farm features a rare kind of grass that, according to discerning cows, is the tastiest in the world. As a result, all cows at the convention want to sample this grass. This will likely lead to long lines, since the pasture is so small that it can accommodate only one cow at a time.
Farmer John knows the time a_i at which each cow plans to arrive at the special pasture, as well as the amount of time t_i she plans to spend sampling the grass once her turn comes. Once cow starts eating, she stays for the full t_i units of time before leaving, and during this time other arriving cows have to wait. If several cows are waiting when the pasture becomes free again, the cow with the highest seniority is allowed to sample the grass next. For this purpose, a cow who arrives exactly when another cow finishes eating is considered to be waiting. Similarly, if several cows arrive at exactly the same time while no cow is eating, the one with the highest seniority eats next.
Help FJ compute the maximum time any cow has to wait in line (between her arrival time a_i and the moment she starts eating).
The first line contains an integer n~(1 \le n \le 10^5). Each of the next lines describes one cow and contains two integers a_i and t_i~(1 \le a_i \le 10^9, 1 \le t_i \le 10^4). The cows are listed in order of seniority, starting with the most senior one.
Print one integer — the maximum waiting time over all cows.
Example 1
In this example, there are cows, numbered in the order they appear in the input. Cow arrives first (at time ), and before she finishes eating (at time ), cows and both arrive. Since cow has higher seniority, she eats next, having waited units of time since her arrival. She finishes at time , and then cow starts eating, having waited units of time since her arrival. After a period during which no cow is eating, cow arrives, and while she is eating, cow arrives; cow starts eating units of time after her arrival. Thus, the cow who waits the longest is cow .