← 返回题目列表

AtCoder · arc094_c

E. 东山和格山

中文机器翻译题面 查看原题

分数: 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