题目描述

UCPC 市有 $N$ 栋房屋，它们以相同间距排列在一条直线上。

安装一根强度为 $x$ 的天线时，可以选择连续的 $l$ 栋房屋为其提供网络，其中 $1\le l\le x$。这 $l$ 栋房屋中的每一栋都会获得

的网络连接速度。

每根天线覆盖的房屋数量 $l$ 可以独立选择。

由于技术限制，每根天线的强度不能超过 $P$。为了避免信号干扰，不允许两根或更多天线覆盖同一栋房屋。

第 $i$ 栋房屋要求至少获得 $a_i$ 的网络连接速度。你需要安装若干天线，使所有房屋的需求都得到满足，并使所有天线强度之和最小。

请输出这个最小值。

输入格式

第一行包含两个整数 $N,P$，分别表示房屋数量和单根天线的最大强度。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示各房屋要求的网络连接速度。

输出格式

输出一个整数，表示满足所有房屋需求时，所有天线强度之和的最小值。

样例

输入

7 5
2 4 3 3 1 4 5

输出

19

样例说明

可以采用以下方案：

• 用一根强度为 $5$ 的天线覆盖第 $1$ 至第 $2$ 栋房屋，每栋获得速度 $4$；
• 用一根强度为 $5$ 的天线覆盖第 $3$ 至第 $5$ 栋房屋，每栋获得速度 $3$；
• 用一根强度为 $4$ 的天线覆盖第 $6$ 栋房屋；
• 用一根强度为 $5$ 的天线覆盖第 $7$ 栋房屋。

总强度为 $5+5+4+5=19$。