Cho mảng gồm \(n\) phần tử \(a_1,a_2,...,a_n\). Và một số nguyên không âm \(x\).

Kaninho thực hiện phép toán dưới đây với số lần bất kì:

• Chọn ra một phần tử \(a_j(1\le j\le n,a_j\ge 1)\) bất kì và giảm nó đi một đơn vị.

Hỏi Kaninho cần thực hiện ít nhất bao nhiêu phép toán để mảng trên thỏa mãn điều kiện sau:

• Hai phần tử bất kỳ liên tiếp nhau phải có tổng không quá \(x\)

Input

• Dòng thứ nhất chứa hai số nguyên \(n,x(2\le n\le 10^5,0\le x\le 10^9)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_i(0\le a_i\le 10^9\ \forall 1\le i\le n)\)

Output

• Số phép toán ít nhất cần thực hiện.

Example

3 3 
2 2 2

1