分数: 200 点
问题陈述
高桥正在电子游戏中探索洞穴。
洞穴包括 N 房间排列成一排。 房间编号为 Room 1,2,\ldots,N 从入口处。
高桥最初在房间里 1,以及 时间限制 is T.
对于每个 1 \leq i \leq N-1,他可能会消耗时间 A_i 从房间搬出 i 到房间 (i+1)。 没有其他方法可以在房间之间移动。
他不能做出超出时间限制的动作 0 或更少。
有 M 洞穴中的奖励房间。 的 i- 第一个奖励房间是房间 X_i;当他到达房间时,时间限制增加了 Y_i.
高桥能到达房间吗 N?
约束
- 2 \leq N \leq 10^5
- 0 \leq M \leq N-2
- 1 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 < X_1 < \ldots < X_M < N
- 1 \leq Y_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
输出
如果高桥能到达房间 N,打印 Yes;否则,打印 No.
示例输入 1
4 1 10 5 7 5 2 10
示例输出 1
Yes
- 高桥最初在房间里 1,时间限制为 10.
- 他消耗了时间 5 移至房间 2。 现在时间限制是 5。 然后,时间限制增加 10;现在是 15.
- 他消耗了时间 7 移至房间 3。 现在时间限制是 8.
- 他消耗了时间 5 移至房间 4。 现在时间限制是 3.
示例输入 2
4 1 10 10 7 5 2 10
示例输出 2
No
他无法离开房间 1 到房间 2.