B - Climbing to the Summit Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、麓から山頂を目指して登山をしています。

麓から山頂までの登山道は N 個の区間に分かれており、各区間にはそれぞれ登りの厳しさを表す難易度が設定されています。 i 番目 (1 \leq i \leq N) の区間の難易度は D_i です。

高橋君は体力 S を持った状態で登山を開始し、区間を 1 番目から N 番目まで順にすべて通過します。途中で体力が 0 以下になっても、登山を中断することなく最後まで進み続けます。

高橋君には「バテた状態」と「バテていない状態」があり、登山開始時はバテていない状態です。一度バテた状態になると、その後体力がいくら回復しても、バテた状態が解除されることはありません。

各区間 i (1 \leq i \leq N) を通過する際、以下の処理がこの順に行われます。

  • 体力の消費： 高橋君がバテていない状態であれば体力が D_i だけ減少し、バテた状態であれば体力が 2 \times D_i だけ減少します。
  • バテ判定： 体力消費後の体力が 0 以下であり、かつ現在バテていない状態であれば、高橋君はバテた状態に変わります。（すでにバテた状態であれば、何も起こりません。）
  • 山小屋での回復： 区間 i を通過した直後に山小屋がある場合、その山小屋の回復量の分だけ体力が増加します。山小屋がない場合、何も起こりません。体力に上限はなく、初期体力を超えて回復することもあります。

登山道の途中にはいくつかの山小屋があります。山小屋は M 個（0 個の場合もあります）あり、 j 番目 (1 \leq j \leq M) の山小屋は区間 P_j を通過した直後に位置しており、体力を R_j だけ回復できます。山小屋は区間 1 から区間 N-1 の通過直後にのみ存在し得ます。区間 N（最後の区間）の通過直後には山小屋はありません。

高橋君がすべての N 区間を通過して山頂に到着したとき、残っている体力を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq N - 1
  • 1 \leq S \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)
  • P_j はすべて異なる
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M S
D_1 D_2 \ldots D_N
P_1 R_1
P_2 R_2
\vdots
P_M R_M
  • 1 行目には、区間の数 N 、山小屋の数 M 、初期体力 S が、スペース区切りで与えられる。
  • 2 行目には、各区間の難易度 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたって、山小屋の情報が与えられる。 M = 0 の場合、この部分は存在しない。
  • 2 + j 行目には、 j 番目の山小屋が位置する区間番号 P_j と、回復量 R_j がスペース区切りで与えられる。山小屋の情報は P_j の昇順で与えられるとは限らない。

出力

高橋君がすべての区間を通過し終えたときの残り体力を 1 行で出力せよ。体力は負の値になることもある。

入力例 1

3 1 10
3 4 2
2 3

出力例 1

4

入力例 2

3 0 5
3 4 2

出力例 2

-6

入力例 3

6 3 20
5 8 3 7 6 4
1 4
3 10
5 3

出力例 3

4

入力例 4

10 4 15
3 5 7 2 8 6 4 9 1 3
2 5
4 3
6 8
8 2

出力例 4

-38

入力例 5

1 0 1
1

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi is climbing from the base of a mountain toward the summit.

The trail from the base to the summit is divided into N sections, each with a difficulty rating representing the severity of the climb. The difficulty of the i-th section (1 \leq i \leq N) is D_i.

Takahashi starts the climb with stamina S and passes through all sections in order from the 1-st to the N-th. Even if his stamina drops to 0 or below during the climb, he continues onward without stopping until the end.

Takahashi can be in either an "exhausted state" or a "non-exhausted state." He starts the climb in a non-exhausted state. Once he becomes exhausted, he remains exhausted for the rest of the climb, regardless of how much stamina he recovers afterward.

When passing through each section i (1 \leq i \leq N), the following steps are performed in this order:

  • Stamina consumption: If Takahashi is in a non-exhausted state, his stamina decreases by D_i. If he is in an exhausted state, his stamina decreases by 2 \times D_i.
  • Exhaustion check: If his stamina after consumption is 0 or below and he is currently in a non-exhausted state, Takahashi becomes exhausted. (If he is already exhausted, nothing happens.)
  • Mountain hut recovery: If there is a mountain hut immediately after passing through section i, his stamina increases by the recovery amount of that hut. If there is no hut, nothing happens. There is no upper limit on stamina, and it can exceed the initial stamina.

There are several mountain huts along the trail. There are M huts (possibly 0), and the j-th hut (1 \leq j \leq M) is located immediately after passing through section P_j, providing a stamina recovery of R_j. Mountain huts can only exist immediately after sections 1 through N-1. There is no mountain hut immediately after section N (the last section).

Determine Takahashi's remaining stamina when he arrives at the summit after passing through all N sections.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq N - 1
  • 1 \leq S \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)
  • All P_j are distinct
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers

Input

N M S
D_1 D_2 \ldots D_N
P_1 R_1
P_2 R_2
\vdots
P_M R_M
  • The first line contains the number of sections N, the number of mountain huts M, and the initial stamina S, separated by spaces.
  • The second line contains the difficulties D_1, D_2, \ldots, D_N of each section, separated by spaces.
  • The following M lines contain information about the mountain huts. If M = 0, this part does not exist.
  • The (2 + j)-th line contains the section number P_j where the j-th mountain hut is located and the recovery amount R_j, separated by spaces. The mountain hut information is not necessarily given in ascending order of P_j.

Output

Output in a single line the remaining stamina of Takahashi after he has passed through all sections. The stamina may be a negative value.

Sample Input 1

3 1 10
3 4 2
2 3

Sample Output 1

4

Sample Input 2

3 0 5
3 4 2

Sample Output 2

-6

Sample Input 3

6 3 20
5 8 3 7 6 4
1 4
3 10
5 3

Sample Output 3

4

Sample Input 4

10 4 15
3 5 7 2 8 6 4 9 1 3
2 5
4 3
6 8
8 2

Sample Output 4

-38

Sample Input 5

1 0 1
1

Sample Output 5

0