C - Mountain Trail Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個の地点からなる山岳トレイルに挑戦しようとしています。地点 1 がスタート地点（麓）、地点 N がゴール地点（山頂）です。

各地点には消耗度が設定されています。地点 i の消耗度は H_i です。高橋君がある地点に到達すると、その地点の消耗度の分だけスタミナが減少します。

また、このトレイルには M 個の補給食が隠されています。j 番目の補給食は地点 P_j にあり、食べるとスタミナが R_j だけ増加します。各地点には補給食は高々 1 個しかなく、各補給食は一度しか食べられません。高橋君がある地点に到達したとき、その地点に補給食がある場合は自動的に入手します。入手した補給食はその場で食べる必要はなく、個数に制限なく持ち運ぶことができます。

高橋君の初期スタミナは K です。スタミナの値に上限はなく、回復によって初期値を超えることもできます。

トレイルは以下の手順で進行します。各地点での処理は消耗 → リタイア判定 → 補給食の入手 → 補給食の使用の順に行われます。リタイア判定とは、その時点でスタミナが 0 未満であればリタイア（失敗）となることです。補給食の使用によるスタミナの増加はリタイア判定の後に行われるため、消耗直後にスタミナが 0 未満である場合はリタイアとなります。

  1. 初期配置： 高橋君は地点 1 からスタートします。地点 1 の消耗度 H_1 の分だけスタミナが減少します。スタミナが 0 未満になった場合はリタイアです。リタイアしなかった場合、地点 1 にある補給食があれば入手し、その後、手持ちの補給食の中から好きな個数（0 個でもよい）を選んで食べることができます。
  2. 移動： 高橋君は現在いる地点 i から、地点 i+1 または地点 i+2 のいずれかに移動します（ただし地点 N を超える地点には移動できません）。地点 i+2 に直接移動した場合、地点 i+1 には立ち寄らないため、地点 i+1 の消耗を受けず、地点 i+1 にある補給食も入手できません。移動先の地点の消耗度の分だけスタミナが減少します。スタミナが 0 未満になった場合はリタイアです。リタイアしなかった場合、移動先の地点にある補給食があれば入手し、その後、手持ちの補給食の中から好きな個数（0 個でもよい）を選んで食べることができます。
  3. 地点 N に到達するまで手順 2 を繰り返します。

補給食を食べることができるのは上記の手順中に示されたタイミング（各地点に到達し消耗を受けリタイア判定を通過した後）のみであり、地点間の移動中には食べることができません。

高橋君がリタイアせずに地点 N に到達できるかどうかを判定してください。到達できる場合は、移動経路の選び方と補給食を食べるタイミングの選び方を最適にしたとき、地点 N に到達した後に残りの手持ちの補給食をすべて食べ終えた時点でのスタミナの最大値を出力してください。到達できない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 10^6
  • 0 \leq M \leq \min(N, 10^5)
  • 0 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq M)
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • P_j はすべて異なる
  • 入力はすべて整数

入力

N M K
H_1 H_2 \cdots H_N
P_1 R_1
P_2 R_2
\vdots
P_M R_M
  • 1 行目には、地点の数 N 、補給食の数 M 、初期スタミナ K がスペース区切りで与えられる。
  • 2 行目には、各地点の消耗度 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
  • 3 行目から M 行にわたり、各補給食の情報が与えられる。 2 + j 行目には、 j 番目の補給食がある地点 P_j と回復量 R_j がスペース区切りで与えられる。

出力

高橋君がリタイアせずに地点 N に到達できる場合は、移動経路と補給食を食べるタイミングを最適に選んだときの、地点 N に到達し残りの手持ちの補給食をすべて食べ終えた後でのスタミナの最大値を 1 行で出力せよ。到達できない場合は -1 を 1 行で出力せよ。

入力例 1

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

出力例 1

4

入力例 2

4 0 3
2 5 5 1

出力例 2

-1

入力例 3

12 5 15
4 7 3 10 2 8 6 1 12 4 5 3
2 10
5 4
7 9
9 20
11 5

出力例 3

21

入力例 4

30 10 25
5 12 4 20 3 15 7 2 25 6 10 4 18 1 9 14 3 22 5 8 16 2 11 7 30 4 6 13 2 10
3 12
5 8
8 5
10 20
14 6
17 15
20 10
24 25
27 7
29 30

出力例 4

75

入力例 5

2 2 0
0 0
1 1000000000
2 1000000000

出力例 5

2000000000

Score : 366 pts

Problem Statement

Takahashi is attempting a mountain trail consisting of N locations. Location 1 is the starting point (foot of the mountain), and location N is the goal (mountain summit).

Each location has an exhaustion level. The exhaustion level of location i is H_i. When Takahashi reaches a location, his stamina decreases by the exhaustion level of that location.

Additionally, M rations are hidden along this trail. The j-th ration is at location P_j, and eating it increases stamina by R_j. There is at most one ration at each location, and each ration can be eaten only once. When Takahashi reaches a location, if there is a ration there, he automatically collects it. He does not need to eat collected rations on the spot and can carry an unlimited number of them.

Takahashi's initial stamina is K. There is no upper limit on stamina, and it can exceed the initial value through recovery.

The trail proceeds according to the following steps. At each location, events occur in the order of Exhaustion \rightarrow Retirement Check \rightarrow Collecting Rations \rightarrow Using Rations. A retirement check means that if stamina is less than 0 at that moment, he retires (fails). Because the stamina increase from using rations occurs after the retirement check, if his stamina is less than 0 immediately after exhaustion, he retires.

  1. Initial Setup: Takahashi starts at location 1. His stamina decreases by the exhaustion level H_1 of location 1. If his stamina becomes less than 0, he retires. If he does not retire, he collects the ration at location 1 if there is one, and then can choose to eat any number (possibly 0) of the rations in his possession.
  2. Movement: From his current location i, Takahashi moves to either location i+1 or location i+2 (he cannot move to a location beyond location N). If he moves directly to location i+2, he does not visit location i+1, so he does not suffer the exhaustion of location i+1, nor does he obtain the ration at location i+1. His stamina decreases by the exhaustion level of the destination location. If his stamina becomes less than 0, he retires. If he does not retire, he collects the ration at the destination location if there is one, and then can choose to eat any number (possibly 0) of the rations in his possession.
  3. Repeat step 2 until reaching location N.

Rations can only be eaten at the timings specified in the steps above (after reaching each location, suffering exhaustion, and passing the retirement check); they cannot be eaten while traveling between locations.

Determine whether Takahashi can reach location N without retiring. If he can, output the maximum possible stamina when he reaches location N and has eaten all remaining rations in his possession, assuming optimal choices of route and timings to eat rations. If he cannot reach location N, output -1.

Constraints

  • 2 \leq N \leq 10^6
  • 0 \leq M \leq \min(N, 10^5)
  • 0 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq N (1 \leq j \leq M)
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • All P_j are distinct.
  • All input values are integers.

Input

N M K
H_1 H_2 \cdots H_N
P_1 R_1
P_2 R_2
\vdots
P_M R_M
  • The first line contains the number of locations N, the number of rations M, and the initial stamina K, separated by spaces.
  • The second line contains the exhaustion levels of each location H_1, H_2, \ldots, H_N, separated by spaces.
  • The next M lines provide information about each ration. The (2 + j)-th line contains the location P_j of the j-th ration and its recovery amount R_j, separated by a space.

Output

If Takahashi can reach location N without retiring, print in a single line the maximum stamina after reaching location N and eating all remaining rations in his possession, assuming optimal choices of route and timings to eat rations. If he cannot reach location N, print -1 in a single line.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

4 0 3
2 5 5 1

Sample Output 2

-1

Sample Input 3

12 5 15
4 7 3 10 2 8 6 1 12 4 5 3
2 10
5 4
7 9
9 20
11 5

Sample Output 3

21

Sample Input 4

30 10 25
5 12 4 20 3 15 7 2 25 6 10 4 18 1 9 14 3 22 5 8 16 2 11 7 30 4 6 13 2 10
3 12
5 8
8 5
10 20
14 6
17 15
20 10
24 25
27 7
29 30

Sample Output 4

75

Sample Input 5

2 2 0
0 0
1 1000000000
2 1000000000

Sample Output 5

2000000000