#3097. 「SNOI2019」通信

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

n 个排成一列的哨站要进行通信。第 i 个哨站的频段为 a_i

每个哨站 i 需要选择以下二者之一:

  1. 直接连接到控制中心,代价为 W
  2. 连接到前面的某个哨站 j(j<i) ,代价为 \lvert a_i - a_j \rvert

每个哨站只能被后面的至多一个哨站连接。

请你求出最小可能的代价和。

输入格式

1 行两个自然数 n, W ,分别表示哨站个数和连接到控制中心的代价;

2 n 个由空格分隔的自然数 a_1, a_2, \dots , a_n 依次表示每个哨站的频段。

输出格式

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

样例

样例输入 1

6 7
8 4 6 1 3 0

样例输出 1

23

样例解释 1

如果用 0 表示控制中心,最优方案中每个哨站向前连接的哨站依次为 0,0,1,2,3,4

样例输入 2

8 4
0 4 2 6 1 5 3 7

样例输出 2

18

样例 3

见附加文件。

数据范围与提示

对于所有数据, 1\le n \le 1000,0\le w,a_i\le 10^9

  • 对于 10\% 的数据, n\le 10
  • 对于另外 10\% 的数据, n\le 20
  • 对于另外 20\% 的数据, n\le 50,W\le 5,a_i\le 4
  • 对于另外 20\% 的数据, n\le 100
  • 对于另外 20\% 的数据, n\le 300
  • 对于余下 20\% 的数据,无特殊限制。