В Берляндии неспокойные времена. Берляндская оппозиция, финансируемая из соседнего государства, организовала митинги в столице Берляндии городе Берляндске. Благодаря работе разведки известно, что митинги продлятся k дней.

К счастью, в Берляндии есть специальный полицейский отряд, который может спасти страну. В нем ровно n солдат, пронумерованных от 1 до n. Берляндский генерал, командующий отрядом, должен составить расписание работы отряда в эти непростые k дней. В каждый из этих дней генерал должен отправить некоторое количество полицейских для разгона беспорядков. Так как отряд большой, а генерал не очень умный, то он может выбрать только набор из всех солдат с номерами от l до r, включительно, где l и r он выбирает произвольно.

Сейчас у генерала есть ровно две проблемы. Во-первых, нельзя два раза отправлять один и тот же отряд — тогда солдатам станет скучно и они взбунтуются. Во-вторых, не все солдаты одинаково надежны. У каждого солдата есть некоторая надежность a_i. Надежность отряда считается как сумма надежностей солдат в нем. Надежность одного солдата может быть отрицательной, тогда при включении в отряд он будет только помехой. Генерал отличается большой жадностью и столь же большой недальновидностью, поэтому каждый день он отправляет на разгон самый надежный отряд солдат из возможных (то есть из всех отрядов, которые еще не были отправлены).

Правительство Берляндии решило узнать, какова будет минимальная надежность отряда, отправляемого на разгон митингов в течение этих k дней. Сам генерал не может справиться со столь сложной задачей. Помогите ему не опозориться перед начальством!