问题 O: 妈妈的礼物

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：132 通过：40

离生日还有m天。此时第i朵花的高度（假设行中的花从左到右从1到n编号）等于ai。在剩下的m天里，zz可以进行一次特殊的浇水，为连续w朵花浇水（他一天只能浇水一次）。在那一天，每朵浇水的花都会生长一个高度单位。zz最终希望最小的花的高度尽可能大。他能得到最小花朵的最大高度是多少？

第一行包含空格分隔的整数n、m和w（1≤w≤n≤10⁵;1.≤m≤10⁵).
第二行包含空格分隔的整数a1，a2，…，an（1≤ai≤10⁹).

打印单个整数− 最小花朵的最大最终高度。

Input

6 2 3
2 2 2 2 1 1

Output

Input

2 5 1
5 8

Output

注意:
第一个样本 beaver可以在第一天浇最后3朵花。第二天他可能根本不浇花了。最后他会得到以下高度:2,2,2,2,2,2。最小的花的高度等于2。这是在这个样例中不可能得到3的高度。

6 2 3
2 2 2 2 1 1