B - Journey of an Electric Vehicle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は電気自動車で長い一本道を走行しようとしています。この道には N 個の区間があり、左から順に区間 1、区間 2、...、区間 N と番号が付けられています。

電気自動車にはバッテリー残量があり、最初のバッテリー残量は K です。高橋君は区間 1 の手前からスタートし、区間 1, 2, \ldots, N を左から順番に走行して区間 N の先まで到達したいと考えています。

各区間の走行は以下のルールに従います。

  • 区間 i を走行するには、走行開始時点でのバッテリー残量が 1 以上でなければなりません。バッテリー残量が 0 以下の場合、それ以上走行することはできず、その時点で旅は終了します。
  • 区間 i を走行すると、バッテリー残量が D_i だけ減少します。ここで D_i はその区間の消費量を表す正の整数です。走行後のバッテリー残量が 0 以下（負の値を含む）になることもありますが、その区間の走行自体は完了します。

道沿いには M 個の充電ステーションがあります。各充電ステーションは異なる位置にあり、充電ステーション j は区間 P_j と区間 P_j + 1 の間に位置しています。高橋君が区間 P_j の走行を完了した直後（区間 P_j + 1 の走行を開始する前）に、この充電ステーションを利用することができます。バッテリー残量が 0 以下であっても充電ステーションは利用できます。

充電ステーションを利用すると、現在のバッテリー残量がいくつであるかに関わらず、バッテリーを新品に交換し、バッテリー残量がちょうど S_j になります。現在のバッテリー残量が S_j より大きい場合でも、交換後の残量は S_j になります。充電ステーションを利用するかどうかは高橋君が自由に選択でき、利用しなくても構いません。

なお、道は一方通行であり、一度通過した地点に戻ることはできません。

高橋君が充電ステーションの利用を適切に選択することで、すべての区間を走行して区間 N の先まで到達できるかどうかを判定してください。区間 N の走行完了後にバッテリー残量が 0 以下であっても、区間 N の走行が完了していれば到達に成功したものとします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq N - 1 (1 \leq j \leq M)
  • 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
  • P_1 < P_2 < \cdots < P_M（充電ステーションは位置の昇順で与えられ、同じ位置に複数の充電ステーションは存在しない）
  • 入力はすべて整数

入力

N M K
D_1 D_2 \ldots D_N
P_1 S_1
P_2 S_2
\vdots
P_M S_M
  • 1 行目には、区間の数 N、充電ステーションの数 M、最初のバッテリー残量 K が、スペース区切りで与えられる。
  • 2 行目には、各区間を走行する際に減少するバッテリー残量 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、充電ステーションの情報が与えられる。M = 0 の場合、この部分は存在しない。
  • 2 + j 行目では、充電ステーション j の位置 P_j と交換後のバッテリー残量 S_j が、スペース区切りで与えられる。

出力

高橋君がすべての区間を走行して区間 N の先まで到達できる場合は Yes を、できない場合は No を出力せよ。

入力例 1

5 2 10
3 4 5 2 3
2 8
4 6

出力例 1

Yes

入力例 2

4 1 5
3 3 3 3
2 4

出力例 2

Yes

入力例 3

10 4 15
5 3 8 2 6 4 7 3 5 2
2 12
4 20
6 10
8 15

出力例 3

Yes

Score : 300 pts

Problem Statement

Takahashi is trying to drive an electric vehicle along a long straight road. This road has N segments, numbered from left to right as segment 1, segment 2, ..., segment N.

The electric vehicle has a battery level, and the initial battery level is K. Takahashi starts just before segment 1 and wants to drive through segments 1, 2, \ldots, N in order from left to right, reaching beyond segment N.

Driving through each segment follows these rules:

  • To drive through segment i, the battery level at the start of driving must be 1 or more. If the battery level is 0 or less, the vehicle cannot drive any further, and the journey ends at that point.
  • Driving through segment i decreases the battery level by D_i, where D_i is a positive integer representing the consumption of that segment. The battery level after driving may become 0 or less (including negative values), but the driving of that segment itself is completed.

There are M charging stations along the road. Each charging station is at a distinct position, and charging station j is located between segment P_j and segment P_j + 1. Takahashi can use this charging station immediately after completing segment P_j (before starting segment P_j + 1). Charging stations can be used even if the battery level is 0 or less.

When a charging station is used, regardless of the current battery level, the battery is replaced with a new one, and the battery level becomes exactly S_j. Even if the current battery level is greater than S_j, the battery level after replacement becomes S_j. Takahashi can freely choose whether or not to use a charging station; it is not mandatory to use it.

Note that the road is one-way, and it is not possible to return to a previously passed point.

Determine whether Takahashi can drive through all segments and reach beyond segment N by appropriately choosing which charging stations to use. Even if the battery level is 0 or less after completing segment N, as long as the driving of segment N is completed, the journey is considered successful.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq N - 1 (1 \leq j \leq M)
  • 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
  • P_1 < P_2 < \cdots < P_M (charging stations are given in ascending order of position, and no two charging stations are at the same position)
  • All input values are integers

Input

N M K
D_1 D_2 \ldots D_N
P_1 S_1
P_2 S_2
\vdots
P_M S_M
  • The first line contains the number of segments N, the number of charging stations M, and the initial battery level K, separated by spaces.
  • The second line contains the battery consumption D_1, D_2, \ldots, D_N for driving each segment, separated by spaces.
  • The following M lines contain information about the charging stations. If M = 0, this part does not exist.
  • The (2 + j)-th line contains the position P_j and the battery level after replacement S_j of charging station j, separated by spaces.

Output

If Takahashi can drive through all segments and reach beyond segment N, print Yes; otherwise, print No.

Sample Input 1

5 2 10
3 4 5 2 3
2 8
4 6

Sample Output 1

Yes

Sample Input 2

4 1 5
3 3 3 3
2 4

Sample Output 2

Yes

Sample Input 3

10 4 15
5 3 8 2 6 4 7 3 5 2
2 12
4 20
6 10
8 15

Sample Output 3

Yes