Tram (Tram)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Xe điện ban đầu rỗng; tại mỗi trạm, ai người xuống trước, bi người lên sau. Tìm số hành khách lớn nhất trên xe sau một trạm (dung lượng tối thiểu). Trạm cuối cho xe rỗng, không có người lên.

Input

2<=n<=1000; n cặp ai,bi thuộc [0,1000]; ai không vượt số đang có, a1=0, bn=0 và ở trạm cuối toàn bộ người còn lại xuống.

Output

Dung lượng tối thiểu cần có (số nguyên).

Subtask

• 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.

Ví dụ

Ví dụ 1

Input

4
0 3
2 5
4 2
4 0

Output

6

Giải thích

Lần lượt số khách còn lại là 3,6,4,0; max=6.

Ví dụ 2

Input

2
0 0
0 0

Output

0

Giải thích

Không ai lên hoặc xuống.