AT_past202107_m.分割

给定一个长度为 $N$ 的整数序列 $A=(A_1,\ A_2,\ \dots,\ A_N)$ 和一个整数 $C$。
定义长度为 $K\ (K\geq 1)$ 的整数序列 $B=(B_1,\ B_2,\ \dots,\ B_K)$ 的分数为：

$$C + \sum_{i=1}^{K-1} |B_{i+1} - B_i|$$

现在需要将整数序列 $A$ 按顺序（顺序不能改变）分成若干个（不要求连续）子序列。

此时，整数序列 $A$ 的总分数定义为所有得到的子序列的分数之和。

请你求出整数序列 $A$ 的总分数的最小值。

输入以如下格式从标准输入读入：

$N$ $C$ $A_1$ $A_2$ $\dots$ $A_N$

输出总分数的最小值。

注意

本题在 2021 年 7 月 17 日 18:00（日本标准时间）之前禁止讨论。如果出现讨论，可能会被要求赔偿。考试结束后可以公开总得分和认证等级，但请不要发布关于解题情况等信息。

约束条件

• $1 \leq N \leq 200$
• $1 \leq C \leq 10^9$
• $1 \leq A_i \leq 10^9$
• 输入均为整数

样例解释 1

可以分解为 $(4, 9),\ (25, 19, 22),\ (1000000000)$。它们各自的分数为 $15, 19, 10$。

样例解释 2

$(3, 1, 4, 1, 5)$ 的分数为 $112$。

由 ChatGPT 4.1 翻译