The Campus Bus
The Campus Bus
For an activity at the University of Puerto Rico at Mayagüez, a bus visits n stops in order. It is empty before the first stop. At stop i, a[i] passengers get off and then b[i] passengers get on.
Find the minimum capacity needed to carry everyone without exceeding it at any time. No passenger gets off unless already on the bus. At the final stop, all remaining passengers get off and nobody gets on.
Input
The first line contains n. Each of the next n lines contains a[i] and b[i], in stop order.
Output
Print one integer: the minimum required capacity.
Constraints
2 ≤ n ≤ 1 000; 0 ≤ a[i], b[i] ≤ 1 000. All inputs satisfy the conditions in the description.
Execution limits
2 s · 256 MiB
Example 1
Input:
5
0 4
1 3
5 2
1 0
2 0
Output:
6
After each stop there are 4, 6, 3, 2 and 0 passengers.
Source
Adapted for OiPR 2026. Fictional Puerto Rican setting. Original problem: https://codeforces.com/problemset/problem/116/A
Scoring
This problem counts as one solved problem only if all test cases pass. No partial credit is awarded.
Comments