Vay bitcoin bán khống

Sắn dự đoán giá một đồng bitcoin (đơn vị USD) trong \(N\) ngày tới là \(d_1, d_2, \dots, d_N\). Bố của Sắn cho phép vay đúng \(1\) bitcoin với các điều kiện sau:

• Phí vay là \(K\) USD cho mỗi ngày vay. Khi trả phải trả lại đúng \(1\) bitcoin.
• Chỉ được thực hiện một lần bán và một lần mua lại.

Sắn có thể vay rồi bán bitcoin vào ngày \(i\), sau đó mua lại vào ngày \(j\) với \(j > i\) (số ngày vay là \(j-i\), tổng phí là \(K \cdot (j-i)\)), lời thu được là \(d_i - d_j - K(j-i)\). Sắn cũng có thể không giao dịch gì nếu không có lời (lời khi đó là \(0\)). Tính số tiền lời lớn nhất Sắn có thể thu.

Input

• Dòng đầu: hai số nguyên \(N\) và \(K\).
• Dòng sau: \(N\) số nguyên \(d_1, \dots, d_N\).

Output

Số tiền lời tối đa.

Constraints

• \(1 \le N \le 2000\)
• \(0 \le K \le 100\)
• \(0 \le d_i \le 10000\)

Sample Input

4 2
20 15 9 3

Sample Output

11

Explanation

Bán ngày \(1\) giá \(20\), mua lại ngày \(4\) giá \(3\), phí \(2\cdot3=6\): lời \(20-3-6=11\).