#2364. 城市美化

内存限制:128 MiB 时间限制:1 Sec

题目描述

城市A需要美化市容市貌,现在有n个楼房排成一列,每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建,使楼房高度得到上升(不能让楼房高度下降),对一栋楼房修建,使其高度上升x,需要x2的费用。
当所有修建完成后,我们把相邻两楼高度的绝对值乘以c(0<=c<=1000),得到的就是城市损失的钱,我们把它同样看作是费用。现在想请你合理安排修建楼房的方案,使得所需费用最小。
 

输入格式

第一行两个数n和c。
接下来n行,每行一个数,表示每栋楼的高度。
 

输出格式

仅一行一个数,表示最小所需的费用。

样例

样例输入


			
5 5
2
2
1
6
8

样例输出


			
31

数据范围与提示

数据范围

对于100%的数据,1<=n<=50000