Present

题目描述

小海狸是一名编程初学者，因此信息学是他最喜欢的科目。很快，他的信息学老师就要过生日了，小海狸决定为老师准备一份礼物。他在窗台上种了一排 $n$ 朵花，并开始等待它们长高。然而，过了一段时间，小海狸发现花不再长高了。他觉得送小花很没有礼貌，于是决定想办法让花长得更高。

距离老师生日还有 $m$ 天。目前第 $i$ 朵花的高度为 $a_{i}$（假设花依次从左到右编号为 $1$ 到 $n$）。在剩下的 $m$ 天里，小海狸每天可以用特殊的浇水工具给连续的 $w$ 朵花浇水（每天只能操作一次）。被浇过水的每一朵花当天都会长高 $1$ 个单位。小海狸想让所有花中最矮的花的高度尽量高。请问，最后所有花中最矮的花最高能有多少高度？

输入格式

第一行包含三个用空格分隔的整数 $n$、$m$ 和 $w$，$(1 \leq w \leq n \leq 10^{5}; 1 \leq m \leq 10^{5})$。
第二行包含 $n$ 个用空格分隔的整数 $a_{1}, a_{2}, ..., a_{n}$，$(1 \leq a_{i} \leq 10^{9})$。

输出格式

输出一个整数，表示所有花中最矮的花最终能达到的最大高度。

输入输出样例 #1

输入 #1

6 2 3
2 2 2 2 1 1

输出 #1

2

输入输出样例 #2

输入 #2

2 5 1
5 8

输出 #2

9

说明/提示

在第一个样例中，小海狸可以在第一天给最后面连续的 $3$ 朵花浇水。第二天可以选择不浇水。最终所有花的高度为：$[2, 2, 2, 3, 2, 2]$。最矮的花高度为 $2$。在本样例中，不可能让最矮的花高度达到 $3$。

由 ChatGPT 5 翻译