题目描述

高橋君はゲームの中で洞窟を探索しています。

洞窟は $N$ 個の部屋が一列に並んだ構造であり、入り口から順に部屋 $1,2,\ldots,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$ $\ldots$ $A_{N-1}$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

高橋君が部屋 $N$ にたどりつくことができるなら Yes を、できないなら No を出力せよ。

题目大意

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

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

小$T$能到达房间$N$吗？

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$
• 入力に含まれる値は全て整数である

Sample Explanation 1

- 高橋君は最初、部屋 $1$ にいて持ち時間は $10$ です。 - 持ち時間を $5$ 消費して部屋 $2$ に移動します。持ち時間は $5$ になります。その後、持ち時間が $10$ 増え $15$ になります。 - 持ち時間を $7$ 消費して部屋 $3$ に移動します。持ち時間は $8$ になります。 - 持ち時間を $5$ 消費して部屋 $4$ に移動します。持ち時間は $3$ になります。

Sample Explanation 2

部屋 $1$ から部屋 $2$ へ移動することができません。