← 返回题目列表

AtCoder · abc320_f

I. 燃油往返

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

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