Có $N$ cây măng cụt trồng trên một hàng ngang và được đánh số từ $1$ đến $N$ theo thứ tự từ trái sang phải. Chủ vườn thuê bạn chọn một số cây để thu hoạch. Bạn chỉ được di chuyển theo hướng từ trái sang phải và không được chọn thu hoạch 2 cây ở cạnh nhau.

Khi thu hoạch măng cụt trên cây $i$, bạn sẽ đạt được tiền công $A_i$. Nếu bạn đã thu hoạch cây thứ $i$, tiếp theo muốn thu hoạch cây thứ $j$ $(1 \leq i < j \leq N)$ thì bạn sẽ phải mất chi phí di chuyển từ cây $i$ đến cây $j$ là $C \times (j - i)$.

Số tiền bạn nhận được từ chủ vườn sẽ bằng tổng số tiền công thu hoạch các cây măng cụt trừ đi tổng chi phí di chuyển. Lưu ý: Nếu bạn chỉ chọn 1 cây để thu hoạch hoặc $C = 0$ thì không có chi phí di chuyển.

Yêu cầu: Bạn hãy tìm số tiền lớn nhất có thể nhận được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $C$ $(1 \leq N \leq 10^6; 0 \leq C \leq 10^6)$ như mô tả ở trên, các số cách nhau bởi dấu cách.
• Dòng thứ hai chứa $N$ số nguyên ~A_1, A_2, \dots, A_N~ ~(1 \leq A_i \leq 10^9)~, biểu thị tiền công thu hoạch mỗi cây, các số cách nhau bởi dấu cách.

Kết quả ra

Xuất ra một số nguyên duy nhất là số tiền lớn nhất có thể nhận được.

Ví dụ 1

Dữ liệu

4 0
1 2 3 4

Kết quả

6

Giải thích

Chọn cây $2, 4$ thu hoạch: $2 + 4 - 0 = 6$.

Ví dụ 2

Dữ liệu

7 1
1 2 9 10 1 1 4

Kết quả

11

Giải thích

Thu hoạch cây $4, 7$ được số tiền $10 + 4 - (1 \times 3) = 11$. (Hoặc chọn cây $2, 4, 7$ cũng ra kết quả $11$).