在美丽的 UCPC 市，共有 $n$ 座房屋沿直线等间距排列。第 $i$ 座房屋的居民要求其网络连接速度至少为 $a_i$。新任市长 Dohun 打算安装新的天线，以确保市民能够获得顺畅的网络连接。

当安装一个强度为 $x$ 的天线时，它会为连续的 $\ell$ 座房屋提供 $x - \ell + 1$ 的网络连接速度。其中，接收网络连接的房屋数量 $\ell$ 可以在安装天线时直接设定为一个不超过 $x$ 的整数，并且每台天线都可以设定不同的值。然而，由于技术限制，单台天线的最大强度为 $P$。此外，为了防止无线电干扰，安装天线时必须保证没有任何两台天线为同一座房屋提供网络。

为了满足所有市民的需求，Dohun 希望为每座房屋提供所需的网络连接速度。此外，为了节省城市预算，他旨在最小化所安装天线的强度之和。请帮助 Dohun 计算出满足所有房屋网络连接速度需求所需的天线强度之和的最小值。

输入格式

第一行包含两个整数 $n$ 和 $P$：城市中的房屋数量和单台天线的最大强度 ($1 \le n \le 5 \cdot 10^5$; $1 \le P \le 10^9$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$：每座房屋所需的网络连接速度 ($1 \le a_i \le P$)。

输出格式

输出满足所有房屋网络连接速度需求所需的天线强度之和的最小值。

样例

样例输入 1

7 5
2 4 3 3 1 4 5

样例输出 1

19

说明

通过安装：

• 一台强度为 5 的天线，为第 1 座到第 2 座房屋提供 4 的连接速度，
• 一台强度为 5 的天线，为第 3 座到第 5 座房屋提供 3 的连接速度，
• 一台强度为 4 的天线，为第 6 座房屋提供 4 的连接速度，
• 一台强度为 5 的天线，为第 7 座房屋提供 5 的连接速度，

我们可以使天线强度总和等于 19，从而满足所有房屋的需求。