Score : $550$ points

问题描述

你计划从坐标 $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$ 升燃料时，是否可以完成这个计划。如果可能，找出所需的最小金额。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:39:13