Страна Кекляндия состоит из n прекрасных городов, пронумерованных слева направо числами от 1 до n. Города соединены n - 1 дорогой, при этом дорога номер i соединяет города i и i + 1, а её длина равняется wi километров.
Каждая машина, попадающая в город i сразу получает gi литров бензина. Никакого другого способа получить бензин в Кекляндии не существует.
Президент Кекляндии Кеко нанял вас организовать самую красивую гонку, которая когда-либо происходила в Кекляндии. Пусть гонка проходит между городами l и r (l ≤ r). Гонка будет состоять из двух этапов. На первом этапе машины едут из города l в город r. После этого, на следующий день машины едут из города r в город l. Разумеется, поскольку это гонка, то машины едут к цели напрямик, то есть на первом этапе едут только направо, а на втором этапе едут только налево. Красота гонки равняется r - l + 1, то есть количеству городов на каждом этапе. Топливный бак всех машин имеет бесконечный размер, так что гонщики всё время забирают весь бензин, который им дают.
В начале каждого этапа гонщики начинают с пустым баков (0 литров бензина), но они сразу получают бензин, который выдают при попадании в стартовый город (то есть город l на первом этапе и город r на втором).
Между некоторыми парами городов l и r гонку организовать не получится, поскольку у машины может кончится топливо до того, как она доедет до конца маршрута.
У вас есть k подарков. Каждый раз, когда вы дарите подарок городу i, его значение gi увеличивается на 1. Подарки можно распределять между городами произвольным образом, в том числе дарить несколько подарков одному городу (каждый раз увеличивая gi на один). Какую самую красивую гонку можно организовать?
Примечание
В первом примере вы можете дать один подарок каждому городу и тогда получится организовать гонку между городами 1 и 4.
Во втором примере можно увеличить g5 на 1 и g6 на 4, тогда станет возможной гонка между городами 2 и 8.