探索

题目描述

Takahashi 正在玩一个游戏，在一个洞窟中探索。

洞窟由 $N$ 个房间排成一排组成，房间从入口处依次编号为 $1,2,\ldots,N$。

Takahashi 初始在房间 $1$，时间限制为 $T$。

对于每个 $1 \le i \le N-1$，他可以从房间 $i$ 移动到房间 $i+1$，消耗 $A_i$ 的时间。除此之外没有其他移动房间的方式。 他不能进行会让时间限制变为 $0$ 或更小的移动。

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

Takahashi 能到达房间 $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 能到达房间 $N$，输出 Yes；否则输出 No。

样例

4 1 10
5 7 5
2 10

Yes

Takahashi 初始在房间 $1$，时间限制为 $10$。

移动到房间 $2$ 消耗 $5$，此时时间限制为 $5$。然后时间限制增加 $10$，变为 $15$。

移动到房间 $3$ 消耗 $7$，此时时间限制为 $8$。

移动到房间 $4$ 消耗 $5$，此时时间限制为 $3$。

4 1 10
10 7 5
2 10

No

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

数据范围

• $2 \le N \le 10^5$
• $0 \le M \le N-2$
• $1 \le T \le 10^9$
• $1 \le A_i \le 10^9$
• $1 \lt X_1 \lt \ldots \lt X_M \lt N$
• $1 \le Y_i \le 10^9$
• 输入中的所有值均为整数