← 返回题目列表

Codeforces · 460/C

C. 礼物

中文机器翻译题面 查看原题

小海狸是一名初级程序员,所以信息学是他最喜欢的科目。很快他的信息学老师就要过生日了,海狸决定为她准备一份礼物。他在窗台上一排种了n朵花,然后开始等待它们生长。然而,过了一段时间,海狸发现花朵停止生长了。海狸认为赠送小花是不礼貌的行为。于是他决定想出一些解决办法。

距离生日还有 m 天。此时第 i 朵花(假设该行花从左到右编号为 1 到 n)的高度等于 ai。在剩下的 m 天中,海狸可以进行一次特殊的浇水,并给连续的花朵浇水(他每天只能这样做一次)。那天,每朵浇水的花都会生长一个高度单位。海狸最终希望最小的花的高度尽可能大。他能得到最小的花的最大高度是多少?

输入

第一行包含空格分隔的整数 n、m 和 w (1 ≤ w ≤ n ≤ 105;1 ≤ m ≤ 105)。第二行包含空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。

输出

打印一个整数——最小花的最大最终高度。

示例

输入 #1

6 2 3
2 2 2 2 1 1

输出 #1

2

输入 #2

2 5 1
5 8

输出 #2

9

注意

在第一个样本中,海狸可以在第一天给最后 3 朵花浇水。第二天他可能根本不浇花。最终他将得到以下高度:[2,2,2,3,2,2]。最小的花的高度等于 2。在此测试中不可能获得高度 3。