B - Dungeon Exploration Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君はダンジョンの探索に挑戦します。

ダンジョンには N 個の部屋が一列に並んでおり、左から i 番目の部屋にはモンスターが 1 体います。i 番目のモンスターの強さは H_i で、このモンスターを倒すと体力が P_i だけ回復するアイテムを落とします。

高橋君は部屋 1 から部屋 N まで、番号の小さい順にすべての部屋をちょうど 1 回ずつ訪れます。高橋君の初期体力は S です。体力に上限はありません。

各部屋 i を訪れたとき、以下のルールが自動的に適用されます。高橋君が行動を選択する余地はありません。

  • 現在の体力が H_i 以上の場合、高橋君はそのモンスターを倒す。まず体力が H_i 減少し、その直後に P_i 回復する。すなわち、体力の変化量は -H_i + P_i である。戦闘の直前に体力が H_i 以上あるため、H_i 減少した直後の体力は 0 以上であることが保証される。
  • 現在の体力が H_i 未満の場合、高橋君はそのモンスターを倒すことができず、その部屋を素通りする。この場合、体力は変化しない。

モンスターを倒せなかった部屋 1 つにつき、罰金として C を支払わなければなりません。

すべての N 個の部屋を訪れ終えたとき、高橋君が支払う罰金の合計額を求めてください。すなわち、モンスターを倒せなかった部屋の数を k としたとき、k \times C を出力してください。

制約

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

入力

N S C
H_1 P_1
H_2 P_2
\vdots
H_N P_N
  • 1 行目には、部屋の数を表す N 、高橋君の初期体力を表す S 、部屋 1 つあたりの罰金を表す C が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各部屋の情報が N 行で与えられる。
  • 1 + i 行目では、i 番目のモンスターの強さ H_i と、そのモンスターを倒したときの体力回復量 P_i が、スペース区切りで与えられる。

出力

高橋君が支払う罰金の合計額を 1 行で出力せよ。

入力例 1

3 10 5
3 1
12 5
5 3

出力例 1

5

入力例 2

5 7 100
5 2
3 10
20 5
11 0
1 0

出力例 2

200

入力例 3

8 15 1000000000
10 8
5 3
20 0
8 7
10 10
100 50
1 0
9 5

出力例 3

2000000000

Score : 266 pts

Problem Statement

Takahashi challenges himself to explore a dungeon.

The dungeon has N rooms arranged in a row. The i-th room from the left contains 1 monster. The i-th monster has strength H_i, and upon being defeated, it drops an item that restores P_i health points.

Takahashi visits all rooms exactly once, from room 1 to room N in order of increasing room number. Takahashi's initial health is S. There is no upper limit on health.

When visiting each room i, the following rules are automatically applied. Takahashi has no choice in the matter.

  • If his current health is greater than or equal to H_i, Takahashi defeats the monster. First, his health decreases by H_i, and immediately after, it recovers by P_i. That is, the net change in health is -H_i + P_i. Since his health was at least H_i just before the battle, it is guaranteed that his health is non-negative immediately after the H_i decrease.
  • If his current health is less than H_i, Takahashi cannot defeat the monster and passes through the room. In this case, his health does not change.

For each room where a monster was not defeated, Takahashi must pay a penalty of C.

After visiting all N rooms, determine the total penalty Takahashi must pay. That is, if the number of rooms where the monster was not defeated is k, output k \times C.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq S \leq 10^9
  • 1 \leq C \leq 10^9
  • 1 \leq H_i \leq 10^9
  • 0 \leq P_i \leq 10^9
  • All input values are integers.

Input

N S C
H_1 P_1
H_2 P_2
\vdots
H_N P_N
  • The first line contains N representing the number of rooms, S representing Takahashi's initial health, and C representing the penalty per room, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, information about each room is given over N lines.
  • The (1 + i)-th line contains the strength H_i of the i-th monster and the health recovery amount P_i upon defeating that monster, separated by spaces.

Output

Output the total penalty Takahashi must pay, on a single line.

Sample Input 1

3 10 5
3 1
12 5
5 3

Sample Output 1

5

Sample Input 2

5 7 100
5 2
3 10
20 5
11 0
1 0

Sample Output 2

200

Sample Input 3

8 15 1000000000
10 8
5 3
20 0
8 7
10 10
100 50
1 0
9 5

Sample Output 3

2000000000