【文件读写】本题使用文件读写：输入文件 dplan.in，输出文件 dplan.out。

时间限制：1000ms　内存限制：512MB

项目	内容
输入文件名	dplan.in
输出文件名	dplan.out
可执行文件名	dplan
每个测试点时限	1.0 秒
内存限制	512 MiB
测试点数目	20
是否等分	是

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某水利工程的一段干渠需要完成 $n$ 段施工任务，各段从上游到下游编号为 $1, 2, \dots, n$，第 $i$ 段的施工难度为 $a_i$。工程方把全部 $n$ 段任务划分成若干个首尾相接的连续区间，每个区间作为一个发包单元交给一家施工队承建，每段任务恰好属于一个区间。

每发包一个区间，工程方除支付固定的管理费 $C$ 外，还要按该区间的施工难度结算工程款。区间的施工难度取其中各段难度的最大值，结算金额为区间内最大难度 × 区间长度。即区间 $[l, r]$（$1 \le l \le r \le n$）的发包总费用为

$$C + \max(a_l, a_{l+1}, \dots, a_r) \times (r - l + 1).$$

工程方可以按任意方式划分区间，区间个数不限。请计算完成全部 $n$ 段施工所需支付的总费用的最小值。

输入格式

从文件 dplan.in 中读入数据。

• 第一行两个整数 $n, C$；
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出到文件 dplan.out 中。

输出一行一个整数，表示总费用的最小值。

样例

样例 1 输入

4 2
4 1 1 4

样例 1 输出

16

样例 2 输入

6 5
5 2 2 2 2 5

样例 2 输出

33

样例 2 解释

按第 1 段、第 2~5 段、第 6 段三个区间发包：管理费共 $3 \times 5 = 15$；三个区间的工程款分别为 $5 \times 1 = 5$、$\max(2,2,2,2) \times 4 = 8$、$5 \times 1 = 5$，合计 $15 + 5 + 8 + 5 = 33$。

样例 3 输入

6 7
6 5 4 3 2 1

样例 3 输出

41

样例 3 解释

按第 1~3 段、第 4~6 段两个区间发包：管理费共 $2 \times 7 = 14$；两个区间的工程款分别为 $\max(6,5,4) \times 3 = 18$、$\max(3,2,1) \times 3 = 9$，合计 $14 + 18 + 9 = 41$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$1 \le C \le 10^9$；
• $1 \le a_i \le 10^9$；
• 任意划分方式均合法，答案在 64 位有符号整数范围内。

各测试点的约束如下：

测试点	$n$	特殊性质
$1\sim3$	$\le 300$	无
$4\sim7$	$\le 3000$
$8\sim10$	$\le 10^5$	A
$11\sim13$		B
$14\sim20$		无

• 特殊性质 A：$a$ 单调不增，即 $a_1 \ge a_2 \ge \dots \ge a_n$。
• 特殊性质 B：$a$ 单调不降，即 $a_1 \le a_2 \le \dots \le a_n$。