F - Fuel Round Trip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

数直線上の座標 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) リットルとなります。 各ガソリンスタンドは、往路と復路で合わせて 1 回までしか使うことができません。
はじめに燃料を 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

Score : 550 points

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