Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
У Миши есть массив из n целых чисел. Он хочет выбрать k различных подотрезков в нем так, чтобы для каждого элемента массива нашелся хотя бы один выбранный отрезок, который его содержит.
При этом Миша хочет, чтобы если просуммировать числа на каждом отрезке, а затем просуммировать получившиеся суммы, то итоговая сумма оказалась максимальна.
Входные данные
В первой строке дано два целых числа n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — количество элементов в массиве и количество отрезков, которые нужно выбрать.
Во второй строке дано n целых чисел ai ( - 50 000 ≤ ai ≤ 50 000) — элементы массива.
Выходные данные
Выведите одно целое число — максимальную сумму сумм чисел на отрезках, которую можно достичь, выбрав k отрезков так, что каждый элемент был покрыт хотя бы одним отрезком.