Phòng thủ lâu đài

Một bức tường thành dài gồm $n$ đoạn, đánh số từ $1$ đến $n$. Hiện tại đoạn thứ $i$ có $a_i$ cung thủ đứng gác. Một cung thủ đứng ở đoạn $i$ có thể bắn yểm trợ cho mọi đoạn $j$ thỏa mãn $|i-j|\le r$ (riêng $r=0$ nghĩa là cung thủ chỉ bắn được đúng đoạn mình đứng).

Mức phòng thủ của đoạn $i$ là tổng số cung thủ có thể bắn yểm trợ cho đoạn đó. Độ tin cậy của phương án phòng thủ là giá trị nhỏ nhất trong các mức phòng thủ của tất cả các đoạn.

Bạn không thể di chuyển các cung thủ đang đứng trên tường, nhưng có thêm một lực lượng dự bị gồm $k$ cung thủ có thể bố trí tùy ý vào các đoạn tường. Hãy bố trí lực lượng dự bị sao cho độ tin cậy của phương án phòng thủ là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $r$ và $k$: số đoạn tường, tầm bắn của cung thủ và số cung thủ dự bị.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: số cung thủ hiện có ở mỗi đoạn.

Dữ liệu ra

In ra một số nguyên duy nhất: độ tin cậy lớn nhất có thể đạt được.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $0\le r\le n$
• $0\le k\le {10}^{18}$
• $0\le a_i\le {10}^9$

Ví dụ