Летом у школьников каникулы. Кто-то уезжает на отдых, кто-то — к бабушке или дедушке, а кто-то устраивается на подработку. Этим летом Нура решила, что хочет немного заработать, и устроилась в магазин продавцом-консультантом.

У магазина, где работает Нура, есть план на ближайшие n дней. Для каждого дня менеджер по продажам точно знает, что в i-й день будет выставлено на продажу k_i единиц товара, и что ровно l_i покупателей придет за покупками в магазин в этот день. Кроме того, менеджер уверен, что каждый из пришедших покупателей покупает ровно одну единицу товара либо, если товаров в магазине не осталось, уходит из магазина без покупок. Более того, в связи с тем, что товары в магазине быстро портятся, менеджер установил следующее правило: если в какой-то из дней в магазине часть товаров осталась не купленной, то эти товары отправляются на свалку, а не остаются на следующий день.

В целях рекламы магазина менеджер предложил провести распродажу. Он дал Нуре задание выбрать из ближайших n дней любые f дней, в каждый из которых будет проведена распродажа. В каждый из этих f выбранных дней количество единиц товара, которое будет выставлено на продажу, будет удвоено. Таким образом, если в i-й день по плану магазин должен был выставить на продажу k_i единиц товара, то, если сделать распродажу в этот день, на витрины магазина будет поставлено 2·k_i единиц товара. Следовательно, в дни распродажи существует возможность продать большее количество товара.

Задача Нуры — выбрать ровно f дней так, чтобы максимизировать суммарное количество проданных единиц товара. Она просит вас помочь ей с этой нелегкой задачей!