[SNOI2019]通信

题目描述

$n$ 个排成一列的哨站要进行通信。第 $i$ 个哨站的频段为 $a_i$。 每个哨站 $i$ 需要选择以下二者之一: 1. 直接连接到控制中心,代价为 $W$; 2. 连接到前面的某个哨站 $j$ ($j<i$),代价为 $|a_i-a_j|$。 每个哨站只能被后面的至多一个哨站连接。 请你求出最小可能的代价和。

输入输出格式

输入格式


第 $1$ 行两个自然数 $n,W$,分别表示哨站个数和连接到控制中心的代价; 第 $2$ 行 $n$ 个由空格分隔的自然数 $a_1,a_2,\ldots,a_n$ 依次表示每个哨站的频段。

输出格式


输出 $1$ 行 $1$ 个自然数表示答案。

输入输出样例

输入样例 #1

6 7
8 4 6 1 3 0

输出样例 #1

23

输入样例 #2

8 4
0 4 2 6 1 5 3 7

输出样例 #2

18

说明

对于所有数据,$1 \leq n \leq 1000$,$0 \leq W,a_i \leq 10^9$。 对于 $10\%$ 的数据,$n \leq 10$; 对于另外 $10\%$ 的数据,$n \leq 20$; 对于另外 $20\%$ 的数据,$n \leq 50$,$W \leq 5$,$a_i \leq 4$; 对于另外 $20\%$ 的数据,$n \leq 100$; 对于另外 $20\%$ 的数据,$n \leq 300$; 对于余下 $20\%$ 的数据,无特殊限制。