M - Divide Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ N の整数列 A=(A_1, A_2, \dots ,A_N) と整数 C があります。
長さ K\ (K \geq 1) の整数列 B=(B_1, B_2, \dots ,B_K) の スコア を、以下の式で定義します。

\displaystyle C + \sum_{i=1}^{K-1} |B_{i+1} - B_i|

整数列 A を順序を保ったまま、いくつかの（連続するとは限らない）部分列に分解します。

このとき整数列 A の 合計スコア を、得られた整数列の スコア の総和として定義します。

整数列 A の 合計スコア の最小値を求めてください。

制約

  • 1 \leq N \leq 200
  • 1 \leq C \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N C
A_1 A_2 \dots A_N

出力

合計スコア の最小値を出力せよ。

入力例 1

6 10
4 25 1000000000 9 19 22

出力例 1

44

(4, 9), (25, 19, 22), (1000000000) と分解します。それぞれの スコア は 15, 19, 10 です。

入力例 2

5 100
3 1 4 1 5

出力例 2

112

(3, 1, 4, 1, 5) の スコア は 112 です。

入力例 3

10 5301
6708 1391 3108 7953 7797 2370 7699 1098 2362 2359

出力例 3

17095

Score : 6 points

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have a sequence of N integers A=(A_1, A_2, \dots ,A_N) and an integer C.
Let us define the score of the sequence of K\ (K \geq 1) integers B=(B_1, B_2, \dots ,B_K) as the following:

\displaystyle C + \sum_{i=1}^{K-1} |B_{i+1} - B_i|.

We will decompose the sequence A into some (not necessarily contiguous) subsequences while keeping the relative order of the elements.

Here, let us define the total score as the sum of the scores of the subsequences obtained.

Find the minimum possible total score.

Constraints

  • 1 \leq N \leq 200
  • 1 \leq C \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
A_1 A_2 \dots A_N

Output

Print the minimum possible value of the total score.

Sample Input 1

6 10
4 25 1000000000 9 19 22

Sample Output 1

44

We should divide it into (4, 9), (25, 19, 22), (1000000000). Their scores are 15, 19, 10, respectively.

Sample Input 2

5 100
3 1 4 1 5

Sample Output 2

112

The score of (3, 1, 4, 1, 5) is 112.

Sample Input 3

10 5301
6708 1391 3108 7953 7797 2370 7699 1098 2362 2359

Sample Output 3

17095