Маленький бобренок — начинающий программист, поэтому информатика — его самый любимый предмет. Совсем скоро будет день рождения учительницы по информатике, и бобренок решил приготовить ей подарок. Он посадил n цветков в ряд на подоконнике и стал ждать, пока они вырастут, чтобы собрать букет ко дню рождения учительницы. Однако, спустя некоторое время, бобренок обнаружил, что цветы перестали расти. Бобренок считает, что дарить слишком маленькие цветы некрасиво, поэтому он решил предпринять соответствующие меры.
До дня рождения осталось m дней. Высота i-го цветка (считайте, что цветы в ряду пронумерованы от 1 до n слева направо) в данный момент времени равна ai. В каждый из оставшихся m дней бобренок может один раз с помощью специальной лейки полить w подряд идущих цветков, при этом каждый политый цветок в этот же день вырастает на единицу длины. Теперь бобренок хочет знать: какая максимальная высота может получиться у самого маленького цветка в букете?
Выходные данные
Выведите целое число — максимальную высоту самого маленького цветка в итоге.
Примечание
В первом примере в первый день нужно полить последние 3 цветка, их высота увеличится на 1. В оставшийся день можно вовсе не поливать цветы. В таком случае высоты цветов будут равны: [2, 2, 2, 3, 2, 2]. Высота самого маленького цветка равна 2. Сделать эту высоту равной 3 за 2 дня никак не получится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 3
2 2 2 2 1 1
|
2
|
|
2
|
2 5 1
5 8
|
9
|