样例文件

题目描述

一条汽车生产流水线上有 $N$ 台设备，依次编号为 $1$ ~ $N$。每台设备有一个参数值，设备 $i$ 的参数值为 $A_i$。

为了提高该生产线的效率，现在要对这些设备进行调试。

调试必须在相邻的两台设备之间进行。对于任意两台相邻设备，都必须调试。调试设备 i 和 i+1 的费用为 $|A_i-A_{i+1}|×C$。其中 $C$ 是一个指定的常数。

为了使得调试总费用降低，你可以在调试开始前修改某些设备的参数。对于任意一台设备，你只能增大其参数值。修改参数也是需要费用的。假设一台设备的参数值增加了 $x$ ($x$ 是正整数)，则该次修改需要支付 $x^2$ 的费用。

一旦开始调试，你将不能再修改设备的参数。

求完成全部工作需要的最少总费用是多少？

输入格式

第一行：$N, C$

接下来 $N$ 行，每行一个整数 $A_i$

输出格式

一个整数，表示最少总费用。

样例输入

5 2
2
3
5
1
4

样例输出

15

样例解释

初始参数：

2 3 5 1 4

一种可能的操作方案如下：

修改第 1 台设备的参数为 3，费用为 $(3-2)^2 = 1$

修改第 4 台设备的参数为 3，费用为 $(3-1)^2 = 4$

修改总费用为 $1 + 4 = 5$

修改后的参数：

3 3 5 3 4

调试总费用为 $0 + 4 + 4 + 2 = 10$

总费用为 $5 + 10 = 15$

数据范围

• 5% 的数据：$N ≤ 10， 1 ≤ C ≤ 10， 0 ≤ A_i ≤ 100$

• 5% 的数据：$N ≤ 100， 1 ≤ C ≤ 10， 0 ≤ A_i ≤ 100$

• 15% 的数据：$N ≤ 10^3， 1 ≤ C ≤ 10， 0 ≤ A_i ≤ 100$

• 10% 的数据：$N ≤ 10^4， 1 ≤ C ≤ 10， 0 ≤ A_i ≤ 100$

• 15% 的数据：$N ≤ 10^5， 1 ≤ C ≤ 10， 0 ≤ A_i ≤ 100$

• 50% 的数据：$N ≤ 10^5， 1 ≤ C ≤ 100， 0 ≤ A_i ≤ 100$