Cho dãy số nguyên \(a_1\), \(a_2\),..., \(a_N\). Ở mỗi thao tác ta có thể chọn một phần tử nguyên dương trong dãy và giảm nó xuống \(1\) đơn vị. Hãy lập trình tính số thao tác tối thiểu cần thực hiện để mọi cặp phần tử liên tiếp trong dãy đều có tổng không vượt quá giá trị \(X\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(X\) (\(2\leq N\leq 10^5\), \(0\leq X\leq 10^9\)).

• Dòng tiếp theo chứa \(N\) số nguyên \(a_1\), \(a_2\),..., \(a_N\) (\(0\leq a_i\leq 10^9\)).

Output

• Một số nguyên là số thao tác ít nhất cần thực hiện.

Example

3 3
2 2 2

1

6 1
1 6 1 2 0 4

11

5 9
3 1 4 1 5

0