题目描述

Takahashi 正在玩一款视频游戏，探索一个洞穴。

这个洞穴由 $N$ 个房间组成，房间从入口开始依次编号为房间 $1, 2, \dots, N$。

Takahashi 最初位于房间 $1$，并且有一个 时间限制 $T$。 对于每个 $1 \leq i \leq 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}$

接下来 $M$ 行，每行输入两个整数，分别是 $X_i$ $Y_i$

输出格式

小 $T$ 能到达房间 $N$ 的话就输出 Yes，不能的话就输出 No。

4 1 10
5 7 5
2 10

Yes

4 1 10
10 7 5
2 10

No

提示

数据范围

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

• Takahashi 最初位于房间 $1$，时间限制为 $10$。
• 他消耗 $5$ 的时间移动到房间 $2$，此时时间限制为 $5$。然后，时间限制增加了 $10$，现在为 $15$。
• 他消耗 $7$ 的时间移动到房间 $3$，此时时间限制为 $8$。
• 他消耗 $5$ 的时间移动到房间 $4$，此时时间限制为 $3$。