B - Monster Slaying Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君はRPGゲームをプレイしています。ゲームのステージには N 体のモンスターが一列に並んでおり、左から順に番号 1, 2, \ldots, N が付けられています。モンスター i の強さは D_i で、倒すと報酬として V_i ゴールドを得られます。

高橋君は最初、攻撃力 0、所持ゴールド 0 の状態です。高橋君はモンスターを倒すとそのモンスターの力を吸収し、攻撃力が増加します。以下では、高橋君の現在の攻撃力を h で表します。

高橋君は左端からモンスター 1, 2, \ldots, N の順に、各モンスターをちょうど1回ずつ訪れます。

また、高橋君は「後回しスタック」と呼ばれる空のスタック（LIFO: 最後に追加した要素を最初に取り出すデータ構造）を持っています。スタックに最後に追加された要素（次に取り出される要素）のことを「一番上の要素」と呼びます。

高橋君がモンスター i を訪れたとき、以下のルールに従います。

  • もし D_i > h であれば、攻撃力が足りないためそのモンスターを後回しにします。後回しにしたモンスターは後回しスタックの一番上に追加されます。この場合、後回し解消処理は行いません。
  • もし D_i \leq h であれば、そのモンスターを倒します。倒すと報酬として V_i ゴールドを得て、攻撃力がそのモンスターの強さだけ増加します（h \leftarrow h + D_i）。モンスターを倒した直後、以下の「後回し解消処理」を行います。

後回し解消処理: 以下の操作を、終了条件を満たすまで繰り返します。

  1. 後回しスタックが空であれば、処理を終了します。
  2. スタックの一番上にあるモンスターの強さを確認します。
  • その強さが h 以下であれば、そのモンスターをスタックから取り除いて倒します。倒した際には通常と同様に報酬を得て、攻撃力がそのモンスターの強さだけ増加します。その後、手順 1 に戻ります。
  • その強さが h より大きければ、処理を終了します。

注意: 後回し解消処理では、常にスタックの一番上のみを確認します。一番上のモンスターを倒して取り除くと、その下にあったモンスターが新たに一番上になり、次の確認対象となります。スタックの途中にある要素を飛ばして確認することはありません。

すべてのモンスター 1, 2, \ldots, N を順に訪れ、それぞれについて上記のルールに従った処理を終えた後、最後にもう一度「後回し解消処理」を行います。

この一連の処理がすべて終了した時点で、後回しスタックにモンスターが残っている場合、それらのモンスターは倒せなかったものとして扱います。倒せなかったモンスターからは報酬を得られず、攻撃力の増加もありません。

最終的に高橋君が得られる報酬の合計ゴールド数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • 入力はすべて整数である。

入力

N
D_1 V_1
D_2 V_2
\vdots
D_N V_N
  • 1 行目には、モンスターの数を表す整数 N が与えられる。
  • 2 行目から N + 1 行目では、各モンスターの情報が与えられる。
  • 1 + i 行目では、モンスター i の強さ D_i と報酬 V_i がスペース区切りで与えられる。

出力

高橋君が得られる報酬の合計ゴールド数を 1 行で出力せよ。

入力例 1

5
0 10
3 20
1 15
0 5
2 30

出力例 1

15

入力例 2

4
5 100
3 50
2 30
1 10

出力例 2

0

入力例 3

8
0 10
0 5
3 20
1 15
2 30
10 100
5 50
4 25

出力例 3

15

入力例 4

12
0 100
0 50
1 200
3 150
2 80
0 10
5 300
4 120
10 500
8 250
6 180
20 1000

出力例 4

160

入力例 5

1
0 1000000000

出力例 5

1000000000

Score : 333 pts

Problem Statement

Takahashi is playing an RPG game. On a game stage, N monsters are lined up in a row, numbered 1, 2, \ldots, N from left to right. Monster i has strength D_i, and defeating it yields a reward of V_i gold.

Takahashi starts with attack power 0 and 0 gold. When Takahashi defeats a monster, he absorbs that monster's power, increasing his attack power. Below, we denote Takahashi's current attack power as h.

Takahashi visits the monsters in order from the left: monster 1, 2, \ldots, N, visiting each monster exactly once.

Additionally, Takahashi has an empty stack called the "postpone stack" (LIFO: a data structure where the last element added is the first to be removed). The element that was added to the stack last (the next element to be removed) is called the "top element."

When Takahashi visits monster i, he follows these rules:

  • If D_i > h, his attack power is insufficient, so he postpones that monster. The postponed monster is added to the top of the postpone stack. In this case, the postpone resolution process is not performed.
  • If D_i \leq h, he defeats that monster. Upon defeating it, he receives a reward of V_i gold, and his attack power increases by that monster's strength (h \leftarrow h + D_i). Immediately after defeating the monster, the following "postpone resolution process" is performed.

Postpone resolution process: Repeat the following operations until the termination condition is met.

  1. If the postpone stack is empty, terminate the process.
  2. Check the strength of the monster on top of the stack.
  • If that strength is h or less, remove that monster from the stack and defeat it. Upon defeating it, receive the reward and increase attack power by that monster's strength, just as usual. Then, return to step 1.
  • If that strength is greater than h, terminate the process.

Note: In the postpone resolution process, only the top of the stack is ever checked. When the top monster is defeated and removed, the monster that was below it becomes the new top and is the next to be checked. Elements in the middle of the stack are never skipped over and checked.

After visiting all monsters 1, 2, \ldots, N in order and performing the above rules for each, one final "postpone resolution process" is performed.

After this entire sequence of operations is complete, if any monsters remain in the postpone stack, they are treated as undefeated. No reward is obtained from undefeated monsters, and no attack power increase occurs.

Determine the total gold Takahashi receives as reward.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • All input values are integers.

Input

N
D_1 V_1
D_2 V_2
\vdots
D_N V_N
  • The first line contains an integer N, representing the number of monsters.
  • Lines 2 through N + 1 provide information about each monster.
  • Line 1 + i contains the strength D_i and reward V_i of monster i, separated by a space.

Output

Print the total gold Takahashi receives as reward in a single line.

Sample Input 1

5
0 10
3 20
1 15
0 5
2 30

Sample Output 1

15

Sample Input 2

4
5 100
3 50
2 30
1 10

Sample Output 2

0

Sample Input 3

8
0 10
0 5
3 20
1 15
2 30
10 100
5 50
4 25

Sample Output 3

15

Sample Input 4

12
0 100
0 50
1 200
3 150
2 80
0 10
5 300
4 120
10 500
8 250
6 180
20 1000

Sample Output 4

160

Sample Input 5

1
0 1000000000

Sample Output 5

1000000000