Bob is creating a snow army to take over the world! Currently, he has ~N~ snowmen in a row with the ~i^\text{th}~ one being ~h_i~ kilometers tall. Bob happens to be an expert snowman builder. He has a special technique in which he can choose exactly ~M~ consecutive snowmen and increase all their heights by ~1~ kilometer each. However, there is only enough snow left to use this technique at most ~K~ times.

You may have heard the old saying that a chain is as strong as its weakest link. This is true for snow armies. The strength of a snow army is equal to the height of the shortest snowman in the army.

Bob has agreed to spare you if you help him. He wants to know the maximum strength his army can obtain with the remaining snow. Can you save yourself?

Constraints

For all subtasks:

~1 \le h_i \le 10^9~

~1 \le M \le N \le 100\,000~

~0 \le K \le 10^9~

Subtask 1 [20%]

~K=1~

Subtask 2 [30%]

~M=1~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain three space-separated integers ~N~, ~M~, and ~K~.
The next line will contain ~N~ space-separated integers ~h_1, h_2, \dots, h_N~.

Output Specification

Output the maximum possible strength.

Sample Input 1

5 2 2
4 3 1 3 4

Sample Output 1

3

Explanation for Sample 1

Bob can first increase the second and third snowmen's heights by ~1~, then increase the third and fourth snowmen's heights by ~1~. After these two changes, the heights are:

4 4 3 4 4

so the strength of this army is ~3~. It is impossible to get a strength higher than ~3~.

Sample Input 2

5 3 1
2 3 3 4 2

Sample Output 2

2