题目描述

你有一个长度为 $n$ 的整数序列 $a$。

现在你可以进行如下操作至多 $m$ 次：将序列中连续的 $w$ 个元素增加 $1$ 。

现在你需要最大化最终序列的最小值。

输入格式

第一行三个整数 $n,m,w$，如题面所述。

第二行一个长 $n$ 的整数序列，表示 $a_i$.

输出格式

一行一个整数，表示最大的最终序列的最小值。

样例

Input # 1

6 2 3
2 2 2 2 1 1

Output # 1

2

Input # 2

2 5 1
5 8

Output # 2

9

数据范围与提示

对于 $100\%$ 数据，有 $1 \leq w \leq n \leq 10 ^ 6,1 \leq m \leq 10^6,1\le a_i\le 10^9$.