問題文

$N$ 個の地点 $1,2,\dots ,N$ が順番に直線上に並んでいて, 地点 $i$ の標高は $H_i$ です。

うしは現在, 地点 $1$ にいます。うしは地点 $1$ 以外の $N-1$ 個の全ての地点を $1$ 回以上訪問したいと考えています。 終了地点はどこでも構いません。

うしは以下の $2$ 種類の操作を, 何度でも行うことができます。

• 隣接する地点に移動する。うしは登山が苦手なので, 現在の地点 $i$ から隣接する地点 $j$ に移動するときエネルギー $max(0,H_j-H_i)$ を消費する。
• ワープして好きな地点に移動する。ワープ $1$ 回につきエネルギー $P$ を消費する。

このとき, 全ての地点を訪問するための最小エネルギーを求めてください。

入力

$N$ $P$
$H_1{H}_2\dots H_N$ 

$1$ 行目に, 地点の数 $N(2\le N\le 200000)$, ワープ $1$ 回のエネルギーの消費量 $P(0\le P\le {10}^9)$ が空白区切りで与えられます。

$2$ 行目に, $N$ 個の整数が空白区切りで与えられます。$i$ 番目の整数 $H_i(0\le H_i\le {10}^9)$ は地点 $i$ の標高を意味します。

出力

$1$ 行に, うしが全ての地点を訪問するための最小エネルギーを出力してください。

サンプル

6 3
1 1 10 10 100 100

3

6 5
100 1 3 0 10 100

7

10 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000

5000000000

4 0
0 1000000000 0 1000000000

0