题目内容

养护队要给一条分成 $L$ 段的护栏做补强。第 $i$ 段当前高度为 $h_i$。手册规定：最多可以施工 $T$ 次；每一次必须选一段连续护栏 $[p,q]$，且长度不超过 $W$，也就是

选中后，该区间内每一段高度都加 1。队里希望补强后「最矮的那段」尽量高。请计算：在不超过 $T$ 次施工时，整条护栏高度最小值能够达到的最大值。

约束写在输入里：段数、次数、窗口与高度都不超过 1000000000。第二行会给出 $L$ 个高度。

输入描述

第一行三个整数 $L$、$T$、$W$，分别表示护栏段数、最多施工次数、单次最多覆盖的连续段数。

第二行 $L$ 个整数 $h_1,h_2,\ldots,h_L$，表示各段初始高度。

其中 $1\le L,W\le 1000000000$，$0\le T,h_i\le 1000000000$。

输出描述

输出一个整数，表示补强后高度最小值的最大可能值。

样例1

输入

4 2 2
3 1 1 3

输出

3

说明

两次施工都盖在中间两段 $[2,3]$，高度变成 $3,3,3,3$，最小值为 3。再抬高做不到。

样例2

输入

1 10 1
5

输出

15

说明

只有一段，十次施工都加在它上面，高度为 $5+10=15$。

样例3

输入

3 0 2
4 2 8

输出

2

说明

不能施工，最小值仍是 2。

数据范围

• $1\le L,W\le 1000000000$
• $0\le T,h_i\le 1000000000$
• 第二行包含 $L$ 个整数
• 所有输入均为整数