施工

construct.cpp/in/out

• 时间限制：1s
• 内存限制：128MB

题目描述

小 Y 家门前有一条街道，街道上顺序排列着 $n$ 幢建筑，其中左起第 $i$ 幢建筑的高度为 $h_i$。

小 Y 定义街道的不美观度为所有相邻建筑高度差的绝对值之和乘上常数 $c$。为了改善街道环境，政府决定进行施工，施工队会选择一些建筑并提升它们的高度，如果一幢建筑最终高度增加了 $t$，则需要花费 $t^2$ 的人力。

小 Y 非常好奇，施工完成后街道的不美观度与施工队花费的人力之和最小为多少。

输入格式

第一行包含两个正整数 $n, c$。

接下来一行 $n$ 个正整数，表示每幢建筑的高度。

输出格式

输出一行一个整数表示答案。

样例输入

4 2
1 3 2 4

样例输出

6

数据范围

对于 100% 的数据，$n, h_i, c \le 1000000$。

• Subtask 1 (11pts)：$n, h_i \le 300$。
• Subtask 2 (19pts)：$n, h_i \le 1000$。
• Subtask 3 (23pts)：$n \le 1000$。
• Subtask 4 (22pts)：$n \le 100000$。
• Subtask 5 (25pts)：无特殊限制。