問題文
高桥最近沉迷于拍摄。
高桥先生 他们正在参加一项比赛,目标是通过射击打破所有 N 气球并获得尽可能少的分数。
对于气球 气球编号最大为 1 它们的编号最大为 N 。 i (1 ≦ i ≦ N) 是比赛开始时的海拔高度。 位于 H_i 随着1 秒过去,高度会增加。 增加 S_i 。
高桥君比赛开始 1 你可以弹出单个气球,然后从那里 1 每秒 您可以弹出 1 气球。高桥可以自由决定爆气球的顺序。
弹出任何气球都会受到惩罚。惩罚是一个整数值,等于气球爆炸的高度。高桥最终得分为 这是 N 气球惩罚的最大值。
求高桥可以获得的最低可能分数。
入力
输入将以以下格式从标准输入提供。
N H_1 S_1 H_2 S_2 : H_N S_N
- 1 行包含一个表示气球数量的整数。 写入 N (1 ≦ N ≦ 100,000) 。
- 2 从行 N 行提供有关气球的信息。N 行数过多 关于第 i (1 ≦ i ≦ N) 第几行包含,2 整数 H_i (1 ≦ H_i ≦ 1,000,000,000), S_i (1 ≦ S_i ≦ 1,000,000,000) 用空格分隔。这是一个气球 i 比赛开始时。 位于 H_i 位于1 秒过去,高度会增加。 增加 S_i 代表增加。
部分点
针对此问题设置了部分分数。
- N ≦ 50 和 所有满足 H_i ≦ 100,000 和 所有满足 S_i ≦ 2,000 的数据集 如果您正确回答 1 , 给出30 点。 如果您正确回答
- 没有附加约束的数据集 2 的回答正确,除上述之外, 70 点。 如果您正确回答
出力
高桥可以获得的最低分数是 1 行输出。还在输出末尾添加换行符。
入力例1
4 5 6 12 4 14 7 21 2
出力例1
23
例如,按如下所示的顺序弹出气球。
- 比赛开始后立即出现气球 除 3 。气球 3 的惩罚是 14 + 7 × 0 = 14 。
- 从比赛开始 1 几秒钟内的气球 4 。气球 4 的惩罚是 21 + 2 × 1 = 23 。
- 从比赛开始 2 几秒钟内的气球 2 。气球 2 的惩罚是 12 + 4 × 2 = 20 。
- 从比赛开始 3 几秒钟内的气球 1 。气球 1 的惩罚是 5 + 6 × 3 = 23 。
由上可知,高桥的得分是 23 ,这是最小值。
入力例2
6 100 1 100 1 100 1 100 1 100 1 1 30
出力例2
105