Vương quốc dưới sự lãnh đạo của nhà vua gồm có \(n\) thành phố nằm cạnh nhau. Mỗi thành phố sẽ có cho mình \(a_i\) trạm phát điện. Với mỗi trạm điện ở thành phố thứ \(i\) nó có thể phát điện được cho các thành phố \(j\) sao cho \(|i - j| \le r\). Ta có năng lượng mà thành phố \(i\) sở hữu là số lượng trạm phát điện có thể phát được tới thành phố \(i\). Gọi độ phát triển của vương quốc là giá trị nhỏ nhất của năng lượng mà các thành phố sở hữu. Vì nhận thấy sự phát triển chưa mạnh mẽ nên nhà vua dự định sẽ cho lắp đặt thêm \(k\) trạm phát điện ở các thành phố bất kì. Hãy giúp nhà vua tính độ phát triển lớn nhất mà vương quốc có thể đạt được.

Input

• Dòng đầu chứa ba số nguyên \(n\), \(r\) và \(k\) (\(1 \le n \le 5 \cdot 10^5\); \(0 \le r \le n\); \(0 \le k \le 10^{18}\)) – Lần lượt là số thành phố, khoảng cách mà các trạm điện có thể phát tới, số trạm phát điện dự tính lắp đặt thêm.
• Dòng thứ hai gồm \(n\) số nguyên \(a_i\) (\(0 \le a_i \le 10^9\)) – Số trạm phát điện ban đầu ở các thành phố.

Output

• In ra một số nguyên duy nhất – Độ phát triển tối đa mà vương quốc có thể đạt được.

Example

5 0 6
4 1 3 2 5

4

10 2 4
2 4 3 1 1 6 6 1 2 6

11

Scoring

• \(40\%\) số điểm có \(r = 0\).
• \(30\%\) số điểm tiếp theo có \(k = 0\).
• \(20\%\) số điểm tiếp theo có \(n, k \le 2 \cdot 10^3\).
• \(10\%\) số điểm còn lại có \(n \le 5 \cdot 10^5\), \(k \le 10^{18}\).