题目描述

有 $n$ 盆花从左往右排成一行，一开始第 $i$ 盆花的高度是 $h[i]$ 。

有一个浇水工具，每次可以对连续的 $k$ 盆花浇水，每浇水一次，花能长高 $1$ 个单位高度。

每天只能使用一次浇水工具。

经过 $m$ 天之后，高度最矮的那盆花的高度尽量要大，输出最矮的那盆花的最大高度。

输入格式

第一行，三个整数 $n$ , $m$ , $k$ ( $1 \le k \le n \le 100000$ , $1 \le m \le 100000$ )。

第二行，$n$ 个整数，第 $i$ 个整数是 $h[i]$ ( $1 \le h[i] \le 10^9$ )。

输出格式

一个整数。

样例

6 2 3
2 2 2 2 1 1

2

2 5 1
5 8

9