問題文
高桥君 我记得 N 魔法。魔法是 它们的编号最大为 1 如果要将其更改为输出最多为 N 。
起初,温度为 0 度。高桥君 当你施展 i 法术时,温度会发生变化。 a_i 升一级后 b_i 度降低。
高桥君把所有的魔法都做得恰到好处。 背诵 1 次。此期间最高气温 X 度。高桥先生设计了施展魔法的顺序, 我正在尝试使X 尽可能小。 找到X 的最小值。
制約
- 1≦N≦10^5
- a_i,b_i 是一个整数。 打印
- 1≦a_i,b_i≦10^9
入力
输入将以以下形式通过标准输入给出。
N a_1 b_1 : a_N b_N
出力
X 的最小值。
入力例1
1 10 20
出力例1
10
当你施展唯一的法术时,温度将会改变。 0 → 10 → -10 它随度数而变化。
入力例2
2 30 20 10 20
出力例2
20
2 第魔法, 如果按顺序施放1 魔法,温度将为 0 → 10 → -10 → 20 → 0 它随度数而变化。
入力例3
5 5 10 10 5 10 15 15 10 20 20
出力例3
10
例如, 你可以按照1,3,5,2,4 法术的顺序施放它们。