B - Travel Budget Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は N 日間の旅行を計画しています。

旅行の 1 日目が始まる前の時点で、高橋君は X 円の所持金を持っています。

各 i 日目 (1 \leq i \leq N) には、次の順に処理が行われます。

  1. A_i 円の収入を得る（日払いのアルバイト代や仕送りなど）。
  2. B_i 円の支出がある（宿泊費や食費など）。

i 日目の処理が始まる直前の所持金を S とすると、i 日目の処理がすべて終わった直後の所持金は S + A_i - B_i 円になります。

1 日目から N 日目まで順に処理を行うとき、すべての i (1 \leq i \leq N) について、i 日目の処理がすべて終わった直後の所持金が 0 以上であるような、0 以上の整数 X の最小値を求めてください。

なお、各日の処理の途中の所持金については条件を問いません。条件として確認するのは、各日の処理がすべて終わった直後の所持金のみです。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 入力はすべて整数である

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、旅行の日数を表す整数 N が与えられる。続く N 行のうち i 行目には、i 日目の収入 A_i と支出 B_i がスペース区切りで与えられる。

出力

条件を満たす初期所持金 X の最小値を整数で 1 行に出力してください。

入力例 1

3
1 3
4 3
2 4

出力例 1

3

入力例 2

4
5 2
0 1
3 3
2 1

出力例 2

0

入力例 3

8
3 7
10 2
1 6
0 3
8 1
2 5
4 4
1 2

出力例 3

4

入力例 4

15
100 300
50 20
0 100
500 10
30 80
1000 1200
200 50
0 500
700 100
60 70
90 400
1000000000 999999900
1 100
500 0
100 600

出力例 4

380

入力例 5

1
0 1000000000

出力例 5

1000000000

Score : 300 pts

Problem Statement

Takahashi is planning a trip lasting N days.

Before the start of day 1 of the trip, Takahashi has X yen in hand.

On each day i (1 \leq i \leq N), the following operations are performed in order:

  1. He receives an income of A_i yen (such as daily wages from a part-time job or an allowance from family).
  2. He has an expenditure of B_i yen (such as accommodation or food costs).

If his amount of money just before the start of day i's operations is S, then his amount of money just after all of day i's operations are completed is S + A_i - B_i yen.

When processing days 1 through N in order, find the minimum value of a non-negative integer X such that for all i (1 \leq i \leq N), the amount of money just after all of day i's operations are completed is at least 0.

Note that there is no condition on the amount of money during the middle of each day's operations. The condition only checks the amount of money just after all of each day's operations are completed.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • All input values are integers

Input

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains an integer N representing the number of days of the trip. Of the following N lines, the i-th line contains the income A_i and expenditure B_i for day i, separated by a space.

Output

Print the minimum value of the initial amount of money X that satisfies the condition, as an integer on a single line.

Sample Input 1

3
1 3
4 3
2 4

Sample Output 1

3

Sample Input 2

4
5 2
0 1
3 3
2 1

Sample Output 2

0

Sample Input 3

8
3 7
10 2
1 6
0 3
8 1
2 5
4 4
1 2

Sample Output 3

4

Sample Input 4

15
100 300
50 20
0 100
500 10
30 80
1000 1200
200 50
0 500
700 100
60 70
90 400
1000000000 999999900
1 100
500 0
100 600

Sample Output 4

380

Sample Input 5

1
0 1000000000

Sample Output 5

1000000000