Bạn sở hữu một mảng \(A\) gồm \(N\) mỏ vàng nằm trên một đường thẳng, \(A_i\) là lượng vàng tại mỏ thứ \(i\). Bạn muốn chọn một đoạn liên tiếp các mỏ từ \(L\) đến \(R\) để khai thác. Tuy nhiên, việc duy trì khai thác tốn kém chi phí. Với mỗi mỏ trong đoạn được chọn, bạn mất \(K\) đơn vị chi phí vận hành.

Lợi nhuận ròng được tính bằng công thức:

Hãy tìm lợi nhuận ròng lớn nhất có thể đạt được (có thể chọn đoạn rỗng với lợi nhuận \(0\)).

Input

• Dòng 1: Hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5, 0 \le K \le 10^9\)).
• Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \le A_i \le 10^9\)).

Output

• Một số nguyên duy nhất là lợi nhuận ròng lớn nhất.

Example

5 4
6 2 5 8 1

5

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 1000\).
• Subtask \(2\) (\(60\%\) số điểm): \(N \le 10^5\).