Fuel Round Trip

题目描述

你计划在数轴上从坐标 $0$ 出发前往坐标 $X_N$，然后折返回到坐标 $0$。在此过程中，去程只能向正方向移动，回程只能向负方向移动。
你将使用汽车旅行。汽车每行驶单位距离消耗一升燃料。你最多可以携带 $H$ 升燃料，且没有燃料时不能移动。
对于每个 $i = 1, 2, \ldots, N-1$，在坐标 $X_i$ 处有一个加油站，可以用 $P_i$ 日元获得 $F_i$ 升燃料。但你不能携带超过 $H$ 升燃料。更精确地说，如果你当前有 $x$ 升燃料并在坐标 $X_i$ 使用该加油站，你必须支付 $P_i$ 日元，且你的燃料量变为 $\min(x + F_i, H)$ 升。每个加油站在整趟往返旅程中最多可以使用一次总共。
判定当你初始有 $H$ 升燃料时是否可以实现该计划，如果可以，求出所需的最少金钱数。

输入格式

输入由标准输入按以下格式提供： $N$ $H$ $X_1$ $X_2$ $\ldots$ $X_N$ $P_1$ $F_1$ $P_2$ $F_2$ $\vdots$ $P_{N-1}$ $F_{N-1}$

输出格式

如果该计划可行，输出所需的最少金钱；否则输出 $-1$。

4 10
2 5 9 11
8 10
5 8
4 9

9

1 1
100000

-1

5 20
4 13 16 18 23
1 16
2 8
4 11
8 13

13

提示

$1 \leq N, H \leq 300$ 0 < X_1 < X_2 < \ldots < X_N \leq 10^5 $1 \leq P_i \leq 10^5$ $1 \leq F_i \leq H$ 所有输入值均为整数。你可以通过在去程使用坐标为 $5$ 的加油站并在回程使用坐标为 $9$ 的加油站来实现该计划，总共支付 $9$ 日元。
支付不超过 $8$ 日元则无法实现该计划。注意你不能在去程和回程中都使用同一个加油站。

标签: AtCoder|abc320F

来源

AtCoder|abc320F