[Usaco2007 Nov]Telephone Wire 架设电话线

时间限制:5s      空间限制:64MB

题目描述

最近,Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务 于是,她们要求FJ把那些老旧的电话线换成性能更好的新电话线。 新的电话线架设在已有的N(2 <= N <= 100,000)根电话线杆上, 第i根电话线杆的高度为height_i米(1 <= height_i <= 100)。 电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端 如果这两根电话线杆的高度不同,那么FJ就必须为此支付 C*电话线杆高度差(1 <= C <= 100)的费用。当然,你不能移动电话线杆, 只能按原有的顺序在相邻杆间架设电话线。Farmer John认为 加高某些电话线杆能减少架设电话线的总花费,尽管这项工作也需要支出一定的费用。 更准确地,如果他把一根电话线杆加高X米的话,他得为此付出X^2的费用。 请你帮Farmer John计算一下,如果合理地进行这两种工作,他最少要在这个电话线改造工程上花多少钱。


输入格式

* 第1行: 2个用空格隔开的整数:N和C

* 第2..N+1行: 第i+1行仅有一个整数:height_i


输出格式

* 第1行: 输出Farmer John完成电话线改造工程所需要的最小花费


样例输入

5 2
2
3
5
1
4
输入说明:
 一共有5根电话线杆,在杆间拉电话线的费用是每米高度差$2。
在改造之前,电话线杆的高度依次为2,3,5,1,4米。



样例输出

15
输出说明:
最好的改造方法是:Farmer John把第一根电话线杆加高1米,把第四根加高2米,
使得它们的高度依次为3,3,5,3,4米。这样花在加高电线杆上的钱是$5。
此时,拉电话线的费用为$2*(0+2+2+1) = $10,总花费为$15。


提示

没有写明提示


题目来源

Gold