分数: 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