Explore

题目描述

Takahashi 正在一个视频游戏中探索一个洞穴。 洞穴由按一排排列的 $N$ 个房间组成。房间从入口处编号为 Room $1,2,\ldots,N$。 Takahashi 最初在 Room $1$，并且时间限制为 $T$。
对于每个 $1 \leq i \leq N-1$，他可以消耗时间 $A_i$ 从 Room $i$ 移动到 Room $(i+1)$。没有其他在房间间移动的方式。 他不能进行会使时间限制变为 $0$ 或更少的移动。 洞穴中有 $M$ 个奖励房间。第 $i$ 个奖励房间是 Room $X_i$；当他到达该房间时，时间限制增加 $Y_i$。 Takahashi 能到达 Room $N$ 吗？

输入格式

输入由标准输入按以下格式提供： $N$ $M$ $T$ $A_1$ $A_2$ $\ldots$ $A_{N-1}$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

如果 Takahashi 能到达 Room $N$，则打印 $Yes$；否则，打印 $No$。

4 1 10
5 7 5
2 10

Yes

4 1 10
10 7 5
2 10

No

提示

$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$ 输入中的所有数值均为整数。Takahashi 最初在 Room $1$，时间限制为 $10$。 他消耗时间 $5$ 移动到 Room $2$。现在时间限制为 $5$。然后，时间限制增加 $10$；现在是 $15$。 他消耗时间 $7$ 移动到 Room $3$。现在时间限制为 $8$。 他消耗时间 $5$ 移动到 Room $4$。现在时间限制为 $3$。
他不能从 Room $1$ 移动到 Room $2$。

标签: AtCoder|abc265B

来源

AtCoder|abc265B