B - 宇宙探査ミッション 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は宇宙探査ロボットを操作して、惑星の表面を調査するミッションに参加しています。ロボットは基地からゴール地点まで一直線のルートを進む必要があります。

ルートの全長は L メートルで、ルート沿いには N 箇所のエネルギーステーションが設置されています。i 番目のエネルギーステーションは基地から P_i メートルの位置にあり、そこでバッテリーを W_i ユニット充電することができます。

ロボットのバッテリー容量は C ユニットで、出発時にはバッテリーが満充電の状態です。ロボットは 1 メートル進むごとに 1 ユニットのエネルギーを消費します。エネルギーステーションに到着したとき、そこで得られるエネルギーをバッテリーに充電できますが、バッテリー容量を超えた分は充電されません。

高橋君はミッション開始前に、各エネルギーステーションの位置と充電量を確認しました。しかし、途中でバッテリーが尽きてしまうとロボットは停止し、ミッション失敗となります。

ロボットがゴール地点に到達したとき、バッテリーに残っているエネルギーの最大値を求めてください。もしゴールに到達できない場合は -1 を出力してください。

制約

  • 1 \leq L \leq 10^9
  • 0 \leq N \leq 2 \times 10^5
  • 1 \leq C \leq 10^9
  • 1 \leq P_i \leq L - 1 (1 \leq i \leq N)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • P_1 < P_2 < \cdots < P_N（エネルギーステーションは基地からの距離の昇順で与えられる）
  • 入力はすべて整数

入力

L N C
P_1 W_1
P_2 W_2
:
P_N W_N
  • 1 行目には、ルートの全長を表す L 、エネルギーステーションの数を表す N 、バッテリー容量を表す C が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各エネルギーステーションの情報が与えられる。
  • 1 + i 行目では、i 番目のエネルギーステーションの基地からの距離 P_i と、そこで得られるエネルギー量 W_i が、スペース区切りで与えられる。
  • エネルギーステーションは基地からの距離の昇順で与えられる。

出力

ロボットがゴール地点に到達したときのバッテリーに残っているエネルギーの最大値を 1 行で出力せよ。ゴールに到達できない場合は -1 を出力せよ。

入力例 1

10 2 8
3 5
7 4

出力例 1

5

入力例 2

20 3 10
5 3
9 2
14 4

出力例 2

-1

入力例 3

100 5 50
10 30
25 20
40 35
60 25
80 15

出力例 3

25

Score : 300 pts

Problem Statement

Takahashi is participating in a mission to investigate the surface of a planet by operating a space exploration robot. The robot needs to travel along a straight route from the base to the goal point.

The total length of the route is L meters, and N energy stations are installed along the route. The i-th energy station is located P_i meters from the base, where the battery can be charged by W_i units.

The robot's battery capacity is C units, and the battery is fully charged at departure. The robot consumes 1 unit of energy for every 1 meter it travels. When the robot arrives at an energy station, it can charge the available energy into its battery, but any amount exceeding the battery capacity will not be charged.

Before the mission begins, Takahashi checked the position and charge amount of each energy station. However, if the battery runs out along the way, the robot will stop and the mission will fail.

Find the maximum amount of energy remaining in the battery when the robot reaches the goal point. If the robot cannot reach the goal, output -1.

Constraints

  • 1 \leq L \leq 10^9
  • 0 \leq N \leq 2 \times 10^5
  • 1 \leq C \leq 10^9
  • 1 \leq P_i \leq L - 1 (1 \leq i \leq N)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • P_1 < P_2 < \cdots < P_N (Energy stations are given in ascending order of distance from the base)
  • All input values are integers

Input

L N C
P_1 W_1
P_2 W_2
:
P_N W_N
  • The first line contains L representing the total length of the route, N representing the number of energy stations, and C representing the battery capacity, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, the information of each energy station is given.
  • The (1 + i)-th line contains the distance P_i of the i-th energy station from the base and the energy amount W_i available there, separated by spaces.
  • Energy stations are given in ascending order of distance from the base.

Output

Output in one line the maximum amount of energy remaining in the battery when the robot reaches the goal point. If the robot cannot reach the goal, output -1.

Sample Input 1

10 2 8
3 5
7 4

Sample Output 1

5

Sample Input 2

20 3 10
5 3
9 2
14 4

Sample Output 2

-1

Sample Input 3

100 5 50
10 30
25 20
40 35
60 25
80 15

Sample Output 3

25