题目描述

小高正在探索一个视频游戏中的洞穴。

洞穴由 $N$ 个房间组成，这些房间排成一排。从入口开始，房间编号为 1 到 $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$ $...$ $A_{N-1}$
$X_1$ $Y_1$
$X_2$ $Y_2$
⋮
$X_M$ $Y_M$

输出格式

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

样例

4 1 10
5 7 5
2 10

Yes

4 1 10
10 7 5
2 10

No

样例解释

【样例1说明】

• 小高最初在房间 1，时间限制为 10。
• 他消耗 5 的时间移动到房间 2。现在时间限制是 5。然后，时间限制增加 10；现在是 15。
• 他消耗 7 的时间移动到房间 3。现在时间限制是 8。
• 他消耗 5 的时间移动到房间 4。现在时间限制是 3。

【样例2说明】

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

数据范围

• $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 < ... < X_M < N$
• $1 \leq Y_i \leq 10^9$
• 所有输入值都是整数。

来源

• AtCoder ABC265B