Problem Description

You are given an integer sequence $A=(A_1,\ A_2,\ \dots\ ,A_N)$ of length $ N $ and an integer $ C $.
The score of an integer sequence $B=(B_1,\ B_2,\ \dots\ ,B_K)$ of length $K\ (K\ \geq\ 1)$ is defined by the following formula:

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

We want to split the integer sequence $ A $ into several (not necessarily contiguous) subsequences while preserving the order.

The total score of the integer sequence $ A $ is defined as the sum of the scores of the obtained subsequences.

Find the minimum total score of the integer sequence $ A $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ C $ $ A_1 $ $ A_2 $ $\dots$ $ A_N $

Output Format

Output the minimum total score.

Sample Input and Output

Sample Input #1

6 10
4 25 1000000000 9 19 22

Sample Output #1

44

Sample Input #2

5 100
3 1 4 1 5

Sample Output #2

112

Sample Input #3

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

Sample Output #3

17095

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 200$
• $1\ \leq\ C\ \leq\ 10^9$
• $1\ \leq\ A_i\ \leq\ 10^9$
• All inputs are integers

Sample Explanation 1

Split into $(4,\ 9),\ (25,\ 19,\ 22),\ (1000000000)$. The scores are $15,\ 19,\ 10$ respectively.

Sample Explanation 2

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

见题面 Input 部分

见题面 Output 部分