题目描述

小红面前有$n$个怪物，站成一排，最初每个怪物有$a_i$的流血状态，小红可以进行$m$次攻击，每次攻击选择$k$个连续的怪物，每个怪物增加 1 层流血状态。小红想知道$m$次攻击之后，流血状态最少的怪物最多可以有多少层流血状态。

输入描述

第一行输入三个整数 $n,m,k$，表示怪物数量，攻击次数，每次攻击选择的怪物数量。 第二行输入$n$个整数 $a_i$，表示每个怪物初始的流血状态。 $1 \leq k \leq n \leq 10^5$ $1 \leq a_i, m \leq 10^9$

输出描述

输出一个整数，表示流血状态最少的怪物最多可以有多少层流血状态。

样例

输入

5 3 2
3 1 2 5 4

输出

4

说明

3 次攻击分别选择 [1, 2], [2, 3], [2, 3]，最后怪物的流血状态为 [4, 4, 4, 5, 4]，流血状态最少的怪物最多有 4 层流血状态。