分数: 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)。击败怪物后,立即出现以下“推迟解决过程”被执行。
推迟解决过程:重复以下操作,直到满足终止条件。
- 如果推迟堆栈为空,则终止进程。
- 检查堆叠顶部怪物的强度。
- 如果那个力量是 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