← 返回题目列表

AtCoder · awc0081_b

B. 怪物屠杀

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

分数: 333 分

问题陈述

高桥正在玩 RPG 游戏。在比赛的舞台上, N 怪物排成一排,编号 1, 2, \ldots, N 从左到右。怪物 i 有实力 D_i,击败它会获得奖励 V_i 黄金。

高桥首发攻击力 0 和 0 黄金。当高桥击败怪物时,他会吸收怪物的力量,增加他的攻击力。下面,我们将高桥当前的攻击力表示为 h.

高桥从左开始按顺序拜访怪物:怪物 1, 2, \ldots, N,访问每个怪物一次。

此外,Takahashi 有一个称为“后置堆栈”的空堆栈(LIFO:最后添加的元素最先被删除的数据结构)。最后添加到堆栈的元素(下一个要删除的元素)称为“顶部元素”。

当高桥拜访怪物时 i,他遵循以下规则:

  • If D_i > h,他的攻击力不足,所以他 推迟 那只怪兽。推迟的怪物被添加到推迟堆栈的顶部。在这种情况下,推迟解决过程是 不 已执行。
  • If D_i \leq h,他 失败 那只怪兽。击败它后,他会获得奖励 V_i 金,其攻击力随该怪兽的力量而增加(h \leftarrow h + D_i)。击败怪物后,立即出现以下“推迟解决过程”被执行。

推迟解决过程:重复以下操作,直到满足终止条件。

  1. 如果推迟堆栈为空,则终止进程。
  2. 检查堆叠顶部怪物的强度。
  • 如果那个力量是 h 以下,将那只怪兽从堆叠中除外并击败它。击败它后,与平常一样,获得奖励并根据该怪物的力量增加攻击力。然后,返回步骤 1。
  • 如果该强度大于 h,终止进程。

注意:在推迟解析过程中,仅检查堆栈顶部。当顶部的怪物被击败并移除时,位于其下方的怪物将成为新的顶部怪物,并且是下一个要检查的怪物。堆栈中间的元素永远不会被跳过和检查。

拜访完所有怪物后 1, 2, \ldots, N 按顺序并为每一个执行上述规则,执行一个最终的“推迟解决过程”。

整个操作序列完成后,如果延迟堆栈中还有剩余怪物,则它们被视为未击败。不败的怪物不会获得奖励,也不会增加攻击力。

确定高桥收到的奖励金币总数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • 所有输入值均为整数。

输入

N
D_1 V_1
D_2 V_2
\vdots
D_N V_N
  • 第一行包含一个整数 N,代表怪物数量。
  • 行 2 通过 N + 1 提供有关每个怪物的信息。
  • 线 1 + i 蕴含力量 D_i 和奖励 怪物的 V_i 怪物的 i,用空格分隔。

输出

在一行中打印高桥收到的奖励金币总额。


示例输入 1

5
0 10
3 20
1 15
0 5
2 30

示例输出 1

15

示例输入 2

4
5 100
3 50
2 30
1 10

示例输出 2

0

示例输入 3

8
0 10
0 5
3 20
1 15
2 30
10 100
5 50
4 25

示例输出 3

15

示例输入 4

12
0 100
0 50
1 200
3 150
2 80
0 10
5 300
4 120
10 500
8 250
6 180
20 1000

示例输出 4

160

示例输入 5

1
0 1000000000

示例输出 5

1000000000