The Campus Bus


Submit solution

Points: 50
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++

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.

Example
Input Example Output Example
5
0 4
1 3
5 2
1 0
2 0
6

After each stop there are 4, 6, 3, 2 and 0 passengers.

Source

Adapted for OiPR 2026. Codeforces 116A — Tram.


Comments

There are no comments at the moment.