P5120 [USACO18DEC] Convention II S

Although Farmer John was delayed for quite a long time picking up arrivals at the airport, the convention he is holding for his grass-loving cows has been going very smoothly so far. The convention has attracted cows from all over the world. However, the highlight of the convention now seems to have caused Farmer John some new scheduling trouble. A very small pasture on his farm produces a type of grass that, according to some knowledgeable cows, is the most delicious in the world. Therefore, all $N$ cows ($1\le N\le 10^5$) attending the convention want to taste this grass. Since the pasture is so small that it can only hold one cow, this may cause a long line. Farmer John knows the time $a_i$ when each cow $i$ plans to arrive at this special pasture, and the amount of time $t_i$ she plans to spend tasting the grass when it is her turn. When cow $i$ starts eating, she will spend the full $t_i$ time before leaving, and any other cows that have arrived must wait in line. If multiple cows are waiting when the pasture becomes free, then the most senior cow will be the next to taste the fresh grass. Here, a cow that arrives exactly when another cow finishes eating and leaves is considered to be "waiting." Similarly, if multiple cows arrive at the same time when no cow is eating, then the most senior cow is the next one to eat. Please help FJ compute the maximum waiting time among all cows (the time from $a_i$ until that cow starts eating).

The first line of input contains $N$. The next $N$ lines give the information of the $N$ cows in order of seniority (the most senior cow is listed first). Each line contains $a_i$ and $t_i$ for one cow. All $t_i$ are positive integers not exceeding $10^4$, and all $a_i$ are positive integers not exceeding $10^9$.

Output the longest waiting time among all cows.

In this example, we have $5$ cows (numbered $1\dots 5$ in the order of the input). Cow $4$ arrives first (at time $10$). Before she finishes eating (at time $27$), cows $1$ and $3$ both arrive. Since cow $1$ is more senior, she eats first, and she waits a total of $2$ time units from her arrival. She finishes eating at time $30$, then cow $3$ starts eating, and she waits a total of $10$ time units from her arrival. After a period when no cow is eating, cow $5$ arrives. While she is eating, cow $2$ also arrives, and can eat after $5$ time units. The cow that waits the longest is cow $3$. Translated by ChatGPT 5