102651: [AtCoder]ABC265 B - Explore

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of $N$ rooms arranged in a row. The rooms are numbered Room $1,2,\ldots,N$ from the entrance.

Takahashi is initially in Room $1$, and the time limit is $T$.
For each $1 \leq i \leq N-1$, he may consume a time of $A_i$ to move from Room $i$ to Room $(i+1)$. There is no other way to move between rooms. He cannot make a move that makes the time limit $0$ or less.

There are $M$ bonus rooms in the cave. The $i$-th bonus room is Room $X_i$; when he arrives at the room, the time limit increases by $Y_i$.

Can Takahashi reach Room $N$?

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $T$
$A_1$ $A_2$ $\ldots$ $A_{N-1}$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

Output

If Takahashi can reach Room $N$, print Yes; otherwise, print No.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

• Takahashi is initially in Room $1$, and the time limit is $10$.
• He consumes a time of $5$ to move to Room $2$. Now the time limit is $5$. Then, the time limit increases by $10$; it is now $15$.
• He consumes a time of $7$ to move to Room $3$. Now the time limit is $8$.
• He consumes a time of $5$ to move to Room $4$. Now the time limit is $3$.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room $1$ to Room $2$.

问题描述

高桥正在一个电子游戏中探索一个洞穴。

这个洞穴由一排$N$个房间组成。这些房间按照从入口开始的顺序编号为Room $1,2,\ldots,N$。

高桥最初在Room $1$，而 时间限制 是$T$。
对于每个$1 \leq i \leq N-1$，他可以消耗一个时间$A_i$从Room $i$移动到Room $(i+1)$。没有其他方式在房间之间移动。 他不能做出使时间限制变为$0$或更少的移动。

这个洞穴中有$M$个奖励房间。第$i$个奖励房间是Room $X_i$；当他到达该房间时，时间限制增加$Y_i$。

高桥可以到达Room $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$

输出

如果高桥可以到达Room $N$，打印Yes；否则，打印No。

样例输入 1

4 1 10
5 7 5
2 10

样例输出 1

Yes

• 高桥最初在Room $1$，而时间限制是$10$。
• 他消耗一个时间$5$移动到Room $2$。现在时间限制是$5$。然后，时间限制增加$10$；现在是$15$。
• 他消耗一个时间$7$移动到Room $3$。现在时间限制是$8$。
• 他消耗一个时间$5$移动到Room $4$。现在时间限制是$3$。

样例输入 2

4 1 10
10 7 5
2 10

样例输出 2

No

他不能从Room $1$移动到Room $2$。