CF460C.Present

Little beaver is a beginner programmer, so informatics is his favorite subject. Soon his informatics teacher is going to have a birthday and the beaver has decided to prepare a present for her. He planted n flowers in a row on his windowsill and started waiting for them to grow. However, after some time the beaver noticed that the flowers stopped growing. The beaver thinks it is bad manners to present little flowers. So he decided to come up with some solutions.

There are m days left to the birthday. The height of the i-th flower (assume that the flowers in the row are numbered from 1 to n from left to right) is equal to a__i at the moment. At each of the remaining m days the beaver can take a special watering and water w contiguous flowers (he can do that only once at a day). At that each watered flower grows by one height unit on that day. The beaver wants the height of the smallest flower be as large as possible in the end. What maximum height of the smallest flower can he get?

小海狸是一名初学编程者，因此信息学是他最喜爱的学科。很快，他的信息学老师就要过生日了，小海狸决定为她准备一份礼物。他在窗台上种下了 $n$ 朵花，排成一排，并开始等待它们生长。然而过了一段时间，小海狸发现这些花停止生长了。他认为送矮小的花是不礼貌的行为，于是决定想出一些解决办法。

距离老师生日还有 $m$ 天。当前第 $i$ 朵花的高度（假设从左到右将这排花编号为 $1$ 到 $n$）为 $a_i$。在剩下的 $m$ 天中，小海狸每天最多可以进行一次特殊的浇水操作，每次可浇灌连续的 $w$ 朵花（即每天至多执行一次该操作）。每次被浇灌的花当天高度增加 $1$ 单位。小海狸希望最终所有花中最矮的那朵花的高度尽可能大。他最终能实现的最矮花的最大可能高度是多少？

The first line contains space-separated integers n, m and w (1 ≤ w ≤ n ≤ 105; 1 ≤ m ≤ 105). The second line contains space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

第一行包含三个用空格分隔的整数 $n$、$m$ 和 $w$（$1 \le w \le n \le 10^5$；$1 \le m \le 10^5$）。第二行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,...,\,a_n$（$1 \le a_i \le 10^9$）。

Print a single integer — the maximum final height of the smallest flower.

输出一个整数——最终最矮花朵的最大高度。

In the first sample beaver can water the last 3 flowers at the first day. On the next day he may not to water flowers at all. In the end he will get the following heights: [2, 2, 2, 3, 2, 2]. The smallest flower has height equal to 2. It's impossible to get height 3 in this test.

在第一个样例中，河狸第一天可以浇灌最后 3 朵花。第二天他可以完全不浇花。最终各朵花的高度为：[2, 2, 2, 3, 2, 2]。最矮的花高度为 2。在此测试用例中，无法使最矮的花高度达到 3。