Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

F. Покрытие массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Миши есть массив из n целых чисел. Он хочет выбрать k различных подотрезков в нем так, чтобы для каждого элемента массива нашелся хотя бы один выбранный отрезок, который его содержит.

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

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

В первой строке дано два целых числа n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — количество элементов в массиве и количество отрезков, которые нужно выбрать.

Во второй строке дано n целых чисел ai ( - 50 000 ≤ ai ≤ 50 000) — элементы массива.

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

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

Пример
Входные данные
5 4
6 -4 -10 -4 7
Выходные данные
11