/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
高橋君はゲームの中で洞窟を探索しています。
洞窟は 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 にたどりつくことができますか？
制約
- 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
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
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 を出力せよ。
入力例 1
4 1 10 5 7 5 2 10
出力例 1
Yes
- 高橋君は最初、部屋 1 にいて持ち時間は 10 です。
- 持ち時間を 5 消費して部屋 2 に移動します。持ち時間は 5 になります。その後、持ち時間が 10 増え 15 になります。
- 持ち時間を 7 消費して部屋 3 に移動します。持ち時間は 8 になります。
- 持ち時間を 5 消費して部屋 4 に移動します。持ち時間は 3 になります。
入力例 2
4 1 10 10 7 5 2 10
出力例 2
No
部屋 1 から部屋 2 へ移動することができません。
Score : 200 points
Problem Statement
Takahashi is exploring a cave in a video game.
The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.
Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms.
He cannot make a move that makes the time limit 0 or less.
There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.
Can Takahashi reach Room N?
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
Output
If Takahashi can reach Room N, print Yes; otherwise, print No.
Sample Input 1
4 1 10 5 7 5 2 10
Sample Output 1
Yes
- Takahashi is initially in Room 1, and the time limit is 10.
- He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
- He consumes a time of 7 to move to Room 3. Now the time limit is 8.
- He consumes a time of 5 to move to Room 4. Now the time limit is 3.
Sample Input 2
4 1 10 10 7 5 2 10
Sample Output 2
No
He cannot move from Room 1 to Room 2.