分数: 550 点
问题陈述
您计划从坐标出发 0 协调 X_N 在数轴上,然后转身返回坐标 0。在此,去程时只能向正方向移动,回程时只能向负方向移动。
您将乘汽车出行。汽车每行驶单位距离消耗一升燃油。您最多可以携带 H 升燃料,没有燃料就无法移动。
对于每个 i = 1, 2, \ldots, N-1,坐标处有加油站 X_i,您可以在哪里获得 F_i 升燃油 P_i 日元。但是,您携带的物品不能超过 H 升燃油。更准确地说,如果你有 x 升燃料并使用坐标处的加油站 X_i,您必须支付 P_i 日元,你的燃料量变成 \min(x + F_i, H) 升。每个加油站最多可使用一次
往返期间总计 往返期间总共.
当你最初有 H 升燃油,如果可能的话,找出所需的最低金额。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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.
示例输入 1
4 10 2 5 9 11 8 10 5 8 4 9
示例输出 1
9
您可以通过坐标处的加油站来实现该计划 5 出境行程和坐标上的一个 9 回程时共支付 9 日元。
通过付费是不可能实现计划的 8 日元以下。请注意,您不能在去程和回程中使用同一个加油站。
示例输入 2
1 1 100000
示例输出 2
-1
示例输入 3
5 20 4 13 16 18 23 1 16 2 8 4 11 8 13
示例输出 3
13