Bob is creating a snow army to take over the world! Currently, he has snowmen in a row with the one being kilometers tall. Bob happens to be an expert snowman builder. He has a special technique in which he can choose exactly consecutive snowmen and increase all their heights by kilometer each. However, there is only enough snow left to use this technique at most 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?
For all subtasks, , , and .
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
No additional restrictions
The first line will contain three space-separated integers , , and .
The next line will contain space-separated integers .
Output the maximum possible strength.
Sample Input 1
5 2 2 4 3 1 3 4
Sample Output 1
Explanation for Sample 1
Bob can first increase the second and third snowmen's heights by , then increase the third and fourth snowmen's heights by . After these two changes, the heights are
4 4 3 4 4
so the strength of this army is . It is impossible to get a strength higher than .
Sample Input 2
5 3 1 2 3 3 4 2
Sample Output 2