题目描述

小 $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}$。

接下来有 $M$ 行，每行输入 $X_i,Y_i$。

输出格式

如果小 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

6 4 5
1 1 1 1 1
2 536870912
3 536870912
4 536870912
5 536870912

Yes

提示

样例说明 1

• 小 T 最初在房间 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\ <\ \ldots\ <\ X_M\ <\ N$
• $1\ \leq\ Y_i\ \leq\ 10^9$
• 所有输入均为整数