Маленький бобренок — начинающий программист, поэтому информатика — его самый любимый предмет. Совсем скоро будет день рождения учительницы по информатике, и бобренок решил приготовить ей подарок. Он посадил n цветков в ряд на подоконнике и стал ждать, пока они вырастут, чтобы собрать букет ко дню рождения учительницы. Однако, спустя некоторое время, бобренок обнаружил, что цветы перестали расти. Бобренок считает, что дарить слишком маленькие цветы некрасиво, поэтому он решил предпринять соответствующие меры.

До дня рождения осталось m дней. Высота i-го цветка (считайте, что цветы в ряду пронумерованы от 1 до n слева направо) в данный момент времени равна a_i. В каждый из оставшихся m дней бобренок может один раз с помощью специальной лейки полить w подряд идущих цветков, при этом каждый политый цветок в этот же день вырастает на единицу длины. Теперь бобренок хочет знать: какая максимальная высота может получиться у самого маленького цветка в букете?