103205: [Atcoder]ABC320 F - Fuel Round Trip

Problem Statement

You are planning to travel from coordinate $0$ to coordinate $X_N$ on a number line, then turn around and return to coordinate $0$. Here, you can only move in the positive direction on the outbound trip and in the negative direction on the return trip.
You will travel by car. The car consumes one liter of fuel for every unit distance it travels. You can carry up to $H$ liters of fuel and cannot move without fuel.
For each $i = 1, 2, \ldots, N-1$, there is a gas station at coordinate $X_i$, where you can get $F_i$ liters of fuel for $P_i$ yen. However, you cannot carry more than $H$ liters of fuel. More precisely, if you have $x$ liters of fuel and use the gas station at coordinate $X_i$, you must pay $P_i$ yen, and your amount of fuel becomes $\min(x + F_i, H)$ liters. Each gas station can be used at most once in total during the round trip.
Determine if you can achieve this plan when you initially have $H$ liters of fuel, and if it is possible, find the minimum amount of money required.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $H$
$X_1$ $X_2$ $\ldots$ $X_N$
$P_1$ $F_1$
$P_2$ $F_2$
$\vdots$
$P_{N-1}$ $F_{N-1}$

Output

If the plan can be achieved, print the minimum amount of money required; otherwise, print -1.

Sample Input 1

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

Sample Output 1

9

You can achieve the plan by using the gas station at coordinate $5$ on the outbound trip and the one at coordinate $9$ on the return trip, paying a total of $9$ yen.
It is impossible to achieve the plan by paying $8$ yen or less. Note that you cannot use the same gas station on both the outbound and return trips.

Sample Input 2

1 1
100000

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

13

问题描述

你计划在数轴上从坐标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$升燃料时，确定你是否可以实现这个计划，如果可以，请找出所需最低金额。

约束

• $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