题目描述

你计划从数轴上的坐标 $0$ 出发，前往坐标 $X_N$，然后折返回到坐标 $0$。在去程时只能向正方向前进，返程时只能向负方向前进。 你将驾驶汽车移动。汽车每行驶 $1$ 距离会消耗 $1$ 升燃料。你最多可以携带 $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。

样例 1

输入

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

输出

9

样例 2

输入

1 1
100000

输出

-1

样例 3

输入

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$
• 所有输入的数值均为整数

样例解释 1

在去程使用坐标 $5$ 处的加油站，返程使用坐标 $9$ 处的加油站，总共支付 $9$ 日元即可完成计划。无法用 $8$ 日元或更少的金额完成计划。注意，去程和返程不能重复使用同一个加油站。

由 ChatGPT 4.1 翻译