燃油往返

题目描述

你计划从坐标 $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

你可以在去程使用坐标 $5$ 处的加油站、返程使用坐标 $9$ 处的加油站来实现计划，总共支付 $9$ 日元。

不可能支付 $8$ 日元或更少来实现计划。注意你不能在去程和返程都使用同一个加油站。

1 1
100000

-1

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

13

数据范围

• $1 \le N, H \le 300$
• $0 \lt X_1 \lt X_2 \lt \ldots \lt X_N \le 10^5$
• $1 \le P_i \le 10^5$
• $1 \le F_i \le H$
• 所有输入值均为整数。