The Campus Bus


Submit solution

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

Author:
Problem type

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

There are no comments at the moment.