木屋效应

题目描述

暴暴龙又把奶龙骗到小屋里面了！这次他将有策略的封锁小屋。

小屋由 $n$ 块木板组成，奶龙逃出小屋的难度取决于最矮的木板高度。

暴暴龙能进行 $k$ 次操作，每次将连续的不超过 $c$ 块木板增高 $1$ 单位高度。

求 $k$ 次操作后，暴暴龙能使得小屋的最矮的木板高度最高是多少。

输入格式

第一行三个整数 $n, k, c$ ，表示木板的数量，操作次数和最多操作的连续木板数。

第二行 $n$ 个整数 $a_i$，表示每块木板的原始高度。

输出格式

一行一个整数，表示最矮的木板高度最高是多少。

输入输出样例

输入 #1

6 2 3
2 2 2 2 1 1

输出 #1

2

输入 #2

2 5 1
5 8

输出 #2

9

说明 / 提示

数据范围与约定

对于 $20\%$ 的数据，满足 $c = 1$.

对于另外 $20\%$ 的数据，满足 $c = 2$.

对于所有的数据，保证 $1\leq n,k,c \leq 1\times10^5, 1 \leq a_i \leq 1\times10^9$.