题目描述

小$T$在洞穴中探险。洞穴有$N$个房间，排成一行，编号为$1$~$N$. 小$T$开始在$1$号洞穴中，他有$t$的时间。 对于每个$i$（$1 \leq i \leq N - 1$）, 他将花费$A_i$的时间从房间$i$移到房间$i+1$. 没有其他的路径。如果时间限制为0或更小，则不能移动。

有$M$个房间有奖励，其中第$i$个有奖励的房间为$X_i$, 当到达第$i$个有奖励的房间后，时限增加$Y_i$.

小$T$能到达房间$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$

输出格式

如果小$T$可以到达 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

提示

约束

评测将采用捆绑测试。

子任务 1：对于 $10\%$ 的测试数据，$M=0$；

子任务 2：对于另外 $20\%$ 的测试数据，$N=3$；

子任务 3：对于 $100\%$ 的测试数据：

• $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

• 小$T$最开始在房间1，时间限制为10。
• 他花费了5的时间移动到房间2。现在时间限制为5。然后，时间限制增加了10；现在时间限制为15。
• 他花费了7的时间移动到房间3。现在时间限制为8。
• 他花费了5的时间移动到房间4。现在时间限制为3。

样例解释 2

他不能从房间1移动到房间2。