分数: 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