← 返回题目列表

AtCoder · arc053_c

C. 巫师高桥

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

問題文

高桥君 我记得 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 法术的顺序施放它们。