分数: 700 点
问题陈述
给定了序列 A 和 B 由非负整数组成。 两者的长度 A 和 B 是 N,以及中元素的总和 A 和 B 相等。 这 i- 第一个元素 A is A_i,以及 i- 第一个元素 B is B_i.
Tozan 和 Gezan 重复以下操作顺序:
- If A 和 B 是相等的序列,终止进程。
- 否则,首先 Tozan 选择一个正元素 A 并将其减少 1.
- 然后,Gezan 在 B 并将其减少 1.
- 然后,给他们的宠物高桥一颗糖果。
Tozan希望在进程终止之前给予高桥的糖果数量尽可能多,而Gezan希望它尽可能少。 求当两人都执行最佳操作时,给予高桥的糖果数量。
约束
- 1 \leq N \leq 2 × 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
输出
打印当 Tozan 和 Gezan 都执行最佳操作时给予 Takahashi 的糖果数量。
示例输入 1
2 1 2 3 2
示例输出 1
2
当 Tozan 和 Gezan 都以最佳方式执行操作时,过程将按如下方式进行:
- 登山减少 A_1 by 1.
- 格赞减少 B_1 by 1.
- 一颗糖果给了高桥。
- 登山减少 A_2 by 1.
- 格赞减少 B_1 by 1.
- 一颗糖果给了高桥。
- As A 和 B 相等,则进程终止。
示例输入 2
3 8 3 0 1 4 8
示例输出 2
9
示例输入 3
1 1 1
示例输出 3
0