← 返回题目列表

AtCoder · abc023_d

D. 射击之王

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

問題文

高桥最近沉迷于拍摄。

高桥先生 他们正在参加一项比赛,目标是通过射击打破所有 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