← 返回题目列表

AtCoder · awc0090_b

B. 太空探索任务

中文机器翻译题面 查看原题

分数: 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
  • 第一行包含 L 代表路线的总长度, N 代表能源站数量,以及 C 代表电池容量,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了各个能源站的信息。
  • 的 (1 + i)第行包含距离 P_i 的 i基地第个能源站及能源量 W_i 在那里可用,用空格分隔。
  • 能源站按距基地距离的升序排列。

输出

在一行中输出机器人到达目标点时电池中剩余的最大能量。如果机器人无法到达目标,则输出 -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