Đoạn con với chi phí theo nhóm

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$ cùng hai số nguyên $m$ và $k$.

Bạn chọn một đoạn con liên tiếp $a_l,a_{l+1},\dots ,a_r$ của dãy. Giá trị của đoạn được tính bằng

$$\sum _{i=l}^r{a}_i-k·\lceil \frac{r-l+1}{m}\rceil ,$$

trong đó $\lceil x\rceil$ là số nguyên nhỏ nhất không nhỏ hơn $x$. Nói cách khác, mỗi khi đoạn dài thêm một nhóm $m$ phần tử (dù nhóm cuối chưa đủ $m$ phần tử) thì phải trả thêm chi phí $k$.

Đoạn rỗng cũng được phép chọn và có giá trị bằng $0$.

Hãy tìm giá trị lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lớn nhất của một đoạn con liên tiếp (có thể rỗng) của dãy.

Ràng buộc

• $1\le n\le 3·{10}^5$
• $1\le m\le 10$
• $1\le k\le {10}^9$
• $-{10}^9\le a_i\le {10}^9$

Ví dụ