The Grass Tasting Queue

Farmer John is hosting a grand conference for his favorite grass‐eating cows. A special type of grass, rumored to be the tastiest in the world, grows in a very small pasture that can only accommodate one cow at a time. All N cows (where \(1 \le N \le 10^5\)) wish to sample this delicious grass.

The situation is as follows: cow \(i\) plans to arrive at time \(a_i\) and, when it is her turn, will spend exactly \(t_i\) time eating the grass. Once a cow begins tasting, she will spend her entire \(t_i\) eating time before leaving, during which any arriving cows must wait in line. When the pasture becomes available, if multiple cows are waiting, the cow with the highest seniority (i.e. the one whose record appears earliest in the input) goes next. Note that if cows arrive exactly at the moment when another cow finishes, they are considered to be waiting. Likewise, if the pasture is empty and multiple cows arrive simultaneously, the one with higher seniority gets to taste first.

Your task is to compute the maximum waiting time among all cows. The waiting time for a cow is defined as the interval from her arrival time \(a_i\) to the time when she starts to taste the grass.

Note: When multiple cows are waiting, the one with the smallest input order (i.e. the more senior cow) is chosen next.

inputFormat

The first line contains a single integer \(N\), the number of cows.

Each of the next \(N\) lines contains two space-separated integers \(a_i\) and \(t_i\), representing the arrival time and the time taken to eat the grass by cow \(i\), respectively.

outputFormat

Output a single integer: the maximum waiting time experienced by any cow.

sample

5
25 3
105 30
20 50
10 17
100 10

10