配点 : $700$ 点

問題文

非負整数からなる数列 $A,B$ が与えられます。 $A,B$ の長さはともに $N$ であり、$A$ の値の総和と $B$ の値の総和は等しいです。 $A$ の $i$ 項目は $A_i$ であり、$B$ の $i$ 項目は $B_i$ です。

とざん君とげざん君は、以下の操作を繰り返します。

• もし $A,B$ が列として等しいなら、繰り返しを終了する
• そうでない場合、まずとざん君が $A$ の正の要素を $1$ つ選び、$1$ 減らす
• その後、げざん君が $B$ の正の要素を $1$ つ選び、$1$ 減らす
• その後、ペットの高橋君に飴を $1$ つ食べさせる

とざん君は繰り返しが終了するまでに高橋君に食べさせる飴の個数を最大に、げざん君は最小にしたいです。 両者最適に操作を行ったとき、高橋君に食べさせる飴の個数を求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i,B_i \leq 10^9(1\leq i\leq N)$
• $A,B$ の値の総和は等しい
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $B_1$

$:$

$A_N$ $B_N$

出力

両者最適に操作を行ったとき、高橋君に食べさせる飴の個数を出力せよ。

2
1 2
3 2

2

両者最適に操作を行ったとき、操作は以下のように進みます。

• とざん君は $A_1$ を $1$ 減らす。
• げざん君は $B_1$ を $1$ 減らす。
• 高橋君に飴を $1$ つ食べさせる。
• とざん君は $A_2$ を $1$ 減らす。
• げざん君は $B_1$ を $1$ 減らす。
• 高橋君に飴を $1$ つ食べさせる。
• $A,B$ が等しくなったので終了する。

3
8 3
0 1
4 8

9

1
1 1

0