AT_abc265_b [ABC265B] Explore

题目描述

高桥君正在游戏中探索洞窟。

洞窟由 $N$ 个房间按一条直线排列，从入口开始依次编号为 $1,2,\ldots,N$。

最初，高桥君在房间 $1$，持有时间为 $T$。 对于每个 $1 \leq i \leq N-1$，高桥君可以消耗 $A_i$ 的持有时间，从房间 $i$ 移动到房间 $i+1$。除此之外，没有其他移动房间的方法。如果移动后持有时间变为 $0$ 或更少，则无法进行该移动。

洞窟中有 $M$ 个奖励房间。第 $i$ 个奖励房间是房间 $X_i$，到达该房间时持有时间会增加 $Y_i$。

高桥君能否到达房间 $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$

输出格式

如果高桥君能够到达房间 $N$，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

4 1 10
5 7 5
2 10

输出 #1

Yes

输入输出样例 #2

输入 #2

4 1 10
10 7 5
2 10

输出 #2

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$
• 输入中的所有数值均为整数。

样例解释 1

• 高桥君最初在房间 $1$，持有时间为 $10$。
• 消耗 $5$ 的持有时间移动到房间 $2$，剩余持有时间为 $5$。随后，持有时间增加 $10$，变为 $15$。
• 消耗 $7$ 的持有时间移动到房间 $3$，剩余持有时间为 $8$。
• 消耗 $5$ 的持有时间移动到房间 $4$，剩余持有时间为 $3$。

样例解释 2

无法从房间 $1$ 移动到房间 $2$。

由 ChatGPT 4.1 翻译