Tram

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A tram starts empty. At each stop, ai people exit before bi people enter. Find the maximum occupancy. At the final stop all leave and no one enters.

Input

2<=n<=1000, pairs 0<=ai,bi<=1000; exiting never exceeds current occupancy, a1=0 and the tram is empty after final stop with bn=0.

Output

The minimum required capacity.

Subtasks

• Subtask 1 (20%): n<=5, mỗi ai,bi<=10.
• Subtask 2 (30%): n<=100, mỗi ai,bi<=100.
• Subtask 3 (50%): n<=1000, mỗi ai,bi<=1000.

Examples

Example 1

Input

4
0 3
2 5
4 2
4 0

Output

6

Explanation

Occupancies are 3,6,4,0, maximum 6.

Example 2

Input

2
0 0
0 0

Output

0

Explanation

The tram remains empty.