Сегодня вам предстоит руководить эльфами-лучниками при обороне крепости от нападения толпы злых орков. С трёх сторон крепость защищена непроходимыми горами, а с оставшейся стороны расположена стена, состоящая из n секций. На текущий момент на i-й секции находится a_i лучников. Известно, что каждый лучник, находящийся на секции i может поражать орков, атакующих секции на расстоянии не более r от данной, то есть секции с номерами j, такие что |i - j| ≤ r. В частности, если r = 0, то лучник может стрелять только в орков, атакующих секцию i.

Защищённостью секции i назовём суммарное количество лучников, которые могут стрелять в орков, атакующих данную секцию. Надёжностью плана обороны называется минимальная величина защищённости какой-либо из секций стены.

До атаки осталось совсем мало времени, и вы не успеваете перерасставить стрелков, уже расположенных на стене. Тем не менее, у вас имеется резерв из k лучников, которых можно распределить по секциям прозвольным образом. Вас интересует, какое максимальное значение надёжности плана обороны можно получить.