Migrated from Lutece 2784 强迫症患者

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

五一收假回来的 MichaelZona 现在不卖瓜了，他换了身行头，开始在天桥旁边卖花。

有一天，刚卷完的 laduiw 的从天桥边路过，看着 MichaelZona 身前的一排花瓶陷入了沉思。他将这一排花瓶从 $1$ 到 $n$ 进行了编号，编号为 $i$ 的花瓶里面有 $a_i$ 束花。laduiw 是一个有强迫症的人，他想让这 $n$ 个花瓶中的花的数目是严格单调递增的。 对于每次操作，laduiw 可以让 MichaelZona 向任意一个花瓶中插入若干束花，并向 MichaelZona 缴纳 $w$ 元（这是一个常数）。laduiw 想让自己花费的钱最少，所以请聪明的你帮他算一下这个最小值是多少。

注意：插花可以插入负数朵，最后花瓶内也可以剩负数朵花。

Input

输入第一行为两个整数 $n, w$。

输入第二行为 $n$ 个整数，分别表示 $a_i$。

Output

输出为 $1$ 行，表示结果。

Samples

3 3
1 3 2

3

Constraints

$1 \leq n \leq 100000$

$1 \leq w \leq 100000$

$1 \leq a_i \leq 10^9$

Resources

2022 UESTC ICPC Training for Dynamic Programming