题目描述

给定两个由非负整数组成的数列 $A,B$，它们的长度均为 $N$，且 $A$ 的所有元素之和与 $B$ 的所有元素之和相等。$A$ 的第 $i$ 项记为 $A_i$，$B$ 的第 $i$ 项记为 $B_i$。

“とざん君”和“げざん君”会重复进行以下操作：

• 如果 $A$ 和 $B$ 作为数列完全相等，则操作结束。
• 否则，首先“とざん君”从 $A$ 中选择一个正数元素，将其减 $1$。
• 然后“げざん君”从 $B$ 中选择一个正数元素，将其减 $1$。
• 接着让宠物“高桥君”吃一颗糖果。

“とざん君”希望在操作结束前让高桥君吃到最多的糖果，而“げざん君”则希望让高桥君吃到最少的糖果。请在双方都采取最优策略的情况下，求高桥君最终能吃到的糖果数量。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

输出格式

输出在双方都采取最优策略时，高桥君能吃到的糖果数量。

样例 1

输入

2
1 2
3 2

输出

2

样例 2

输入

3
8 3
0 1
4 8

输出

9

样例 3

输入

1
1 1

输出

0

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i, B_i \leq 10^9\ (1 \leq i \leq N)$
• $A$ 和 $B$ 的元素之和相等
• 输入均为整数

样例解释 1

在双方都采取最优策略时，操作过程如下：

• “とざん君”将 $A_1$ 减 $1$。
• “げざん君”将 $B_1$ 减 $1$。
• 高桥君吃到 $1$ 颗糖果。
• “とざん君”将 $A_2$ 减 $1$。
• “げざん君”将 $B_1$ 减 $1$。
• 高桥君吃到 $1$ 颗糖果。
• 此时 $A$ 和 $B$ 相等，操作结束。

由 ChatGPT 4.1 翻译