Background

小 $Q$ 去爬山啦！

Description

小 $Q$ 有两种方式爬山：

1.爬 从一个山峰爬到相邻山峰，花费 $\max(0, h_i - h_j)$。

2.瞬移 移到任意一个山峰，花费 $P$

小 $Q$ 想知道他从 $1$ 号山峰开始经过 $n$ 个山峰所需要的最小体力。

Format

Input

第一行两个整数 $n, P$。 然后 $n$ 个数字，代表山峰的高度 $h_i$。

Output

一行，代表答案

Samples

6 5
100 1 3 0 10 100

7

Limitation

$2 \le n \le 5 \times 10^5$

$0 \le P \le 10^{10}$

$0 \le h_i \le 10^{20}$

保证答案不超 long long。