Страна Кекляндия состоит из n прекрасных городов, пронумерованных слева направо числами от 1 до n. Города соединены n - 1 дорогой, при этом дорога номер i соединяет города i и i + 1, а её длина равняется w_i километров.

Каждая машина, попадающая в город i сразу получает g_i литров бензина. Никакого другого способа получить бензин в Кекляндии не существует.

Президент Кекляндии Кеко нанял вас организовать самую красивую гонку, которая когда-либо происходила в Кекляндии. Пусть гонка проходит между городами l и r (l ≤ r). Гонка будет состоять из двух этапов. На первом этапе машины едут из города l в город r. После этого, на следующий день машины едут из города r в город l. Разумеется, поскольку это гонка, то машины едут к цели напрямик, то есть на первом этапе едут только направо, а на втором этапе едут только налево. Красота гонки равняется r - l + 1, то есть количеству городов на каждом этапе. Топливный бак всех машин имеет бесконечный размер, так что гонщики всё время забирают весь бензин, который им дают.

В начале каждого этапа гонщики начинают с пустым баков (0 литров бензина), но они сразу получают бензин, который выдают при попадании в стартовый город (то есть город l на первом этапе и город r на втором).

Между некоторыми парами городов l и r гонку организовать не получится, поскольку у машины может кончится топливо до того, как она доедет до конца маршрута.

У вас есть k подарков. Каждый раз, когда вы дарите подарок городу i, его значение g_i увеличивается на 1. Подарки можно распределять между городами произвольным образом, в том числе дарить несколько подарков одному городу (каждый раз увеличивая g_i на один). Какую самую красивую гонку можно организовать?