← 返回题目列表

AtCoder · awc0020_b

B. 攀登顶峰

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

分数: 266 分

问题陈述

高桥正在从山脚向山顶攀登。

从山脚到山顶的步道分为 N 部分,每个部分都有一个代表攀爬严重程度的难度等级。的难度 i第节 (1 \leq i \leq N) is D_i.

高桥以体力开始攀登 S 并按顺序遍历所有部分 1-st 到 N-th。即使他的体力下降到 在攀登过程中 0 或以下,他继续前行,不停歇,直到终点。

高桥可以处于“疲惫状态”或“非疲惫状态”。他在不疲惫的状态下开始攀登。一旦他筋疲力尽,无论他之后恢复了多少体力,他在接下来的攀爬中仍然会筋疲力尽。

经过各路段时 i (1 \leq i \leq N),按此顺序执行以下步骤:

  • 体力消耗: 如果高桥处于非疲惫状态,他的体力会减少 D_i。如果他处于疲惫状态,他的体力会减少 2 \times D_i.
  • 耗尽检查: 如果他消耗后的体力是 0 或以下并且他目前处于非疲惫状态,高桥变得疲惫。 (如果他已经筋疲力尽,则什么也不会发生。)
  • 山间小屋恢复: 如果穿过路段后立即有山间小屋 i,他的体力增加了该小屋的恢复量。如果没有小屋,什么也不会发生。体力没有上限,可以超过初始体力。

沿途有几间山间小屋。有 M 小屋(可能 0),以及 j第一个小屋 (1 \leq j \leq M) 位于穿过部分后立即 P_j,提供耐力恢复 R_j。山间小屋只能在部分之后立即存在 1 通过 N-1。过了一段就没有山间小屋了 N (最后一节)。

确定高桥在完成所有任务后到达山顶时的剩余体力 N 部分。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq N - 1
  • 1 \leq S \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq N - 1 (1 \leq j \leq M)
  • 全部 P_j 是不同的
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • 所有输入值均为整数

输入

N M S
D_1 D_2 \ldots D_N
P_1 R_1
P_2 R_2
\vdots
P_M R_M
  • 第一行包含节数 N, 山间小屋数量 M,以及初始耐力 S,用空格分隔。
  • 第二行包含困难 每个部分的 D_1, D_2, \ldots, D_N ,以空格分隔。
  • 以下 M 行包含有关山间小屋的信息。如果 M = 0,这部分不存在。
  • 的 (2 + j)- 第行包含节号 P_j 哪里 j第山间小屋所在位置及回收金额 R_j,用空格分隔。山间小屋信息不一定按升序给出 P_j.

输出

单行输出高桥通过所有路段后剩余的体力。耐力可能为负值。


示例输入 1

3 1 10
3 4 2
2 3

示例输出 1

4

示例输入 2

3 0 5
3 4 2

示例输出 2

-6

示例输入 3

6 3 20
5 8 3 7 6 4
1 4
3 10
5 3

示例输出 3

4

示例输入 4

10 4 15
3 5 7 2 8 6 4 9 1 3
2 5
4 3
6 8
8 2

示例输出 4

-38

示例输入 5

1 0 1
1

示例输出 5

0