题目描述

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

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

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

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

输入格式

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

$N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出格式

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

题目大意

有两个数组，他们数据个数和总和均相等。两个人进行如下操作：

1. 若两个数组相等，则停止操作。
2. 第一个人在 $a$ 数组任选一个数，将其 $-1$ 。
3. 第二个人在 $b$ 数组任选一个数，将其 $-1$ 。

第一个人想尽可能的增加操作次数，第二个人想尽可能的减少操作次数。求在最优情况下的操作次数。

数列长度 $\leq 2\times 10^5$，$1\leq a_i,b_i\leq 10^9$。

2
1 2
3 2

2

3
8 3
0 1
4 8

9

1
1 1

0

提示

制約

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

Sample Explanation 1

両者最適に操作を行ったとき、操作は以下のように進みます。 - とざん君は $A_1$ を $1$ 減らす。 - げざん君は $B_1$ を $1$ 減らす。 - 高橋君に飴を $1$ つ食べさせる。 - とざん君は $A_2$ を $1$ 減らす。 - げざん君は $B_1$ を $1$ 減らす。 - 高橋君に飴を $1$ つ食べさせる。 - $A,B$ が等しくなったので終了する。