E. Разгон митингов
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

Входные данные

На первой строке записаны два целых числа n и k — количество солдат в отряде и количество дежурств.

На второй строке задано n целых чисел через пробел ai, не превосходящих по модулю 109 — надежности солдат.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Выходные данные

Выведите одно число — искомую минимальную надежность отряда в течение этих k дней.

Примеры
Входные данные
3 4
1 4 2
Выходные данные
4
Входные данные
4 6
2 -1 2 -1
Выходные данные
1
Входные данные
8 10
1 -2 3 -4 5 -6 7 -8
Выходные данные
2