机会成本 - Problem

Description

有 $lns="http://www.w3.org/1998/Math/MathML"> N$ 门考试，当复习第 $lns="http://www.w3.org/1998/Math/MathML"> i$ 门考试时，所得分数记为 $lns="http://www.w3.org/1998/Math/MathML"> A_{i}$ ，若不复习，所得分数记为 $lns="http://www.w3.org/1998/Math/MathML"> B_{i}$ ，保证 $lns="http://www.w3.org/1998/Math/MathML"> B_{i} \leq A_{i}$ 。

如果在考试之前，只能复习一门考试，请问应该复习哪一门，才能让所有考试的分数总和达到最大，输出这个最大值。

Input

第一行：单个整数表示 $lns="http://www.w3.org/1998/Math/MathML"> N$ ；
第二行到第 $lns="http://www.w3.org/1998/Math/MathML"> N + 1$ 行：每行两个整数表示 $lns="http://www.w3.org/1998/Math/MathML"> A_{i}$ 与 $lns="http://www.w3.org/1998/Math/MathML"> B_{i}$ 。

对于 $lns="http://www.w3.org/1998/Math/MathML"> 30 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq N \leq 5, 000$ ；
对于 $lns="http://www.w3.org/1998/Math/MathML"> 60 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq N \leq 20, 000$ ；
对于 $lns="http://www.w3.org/1998/Math/MathML"> 100 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq N \leq 500, 000$ ；
$lns="http://www.w3.org/1998/Math/MathML"> 0 \leq B_{i} \leq A_{i} \leq 4000$ ；

Output

单个整数：表示最大的分数之和。

Sample Input Copy

Sample Output Copy

HINT

样例数据1 输入: 3 100 100 80 50 90 80 输出: 260 说明: 复习第二门课

样例数据2 输入: 3 100 100 90 90 80 80 输出: 270 说明: 复习没用

样例数据3 输入: 2 4000 0 4000 0 输出: 4000

Source/Category

循环结构