C. Новая игра плюс!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кролик играет в игру, в которой есть $$$n$$$ боссов, пронумерованных от $$$1$$$ до $$$n$$$. Боссов можно побеждать в любом порядке. Каждого босса нужно победить ровно один раз. Также в игре присутствует параметр, называемый комбо-бонусом, изначально равный $$$0$$$.

Когда игрок побеждает $$$i$$$-го босса, ко счету игрока добавляется текущее значение комбо-бонуса, а затем значение комбо-бонуса изменяется на величину $$$c_i$$$. Обратите внимание, что величина $$$c_i$$$ может быть отрицательной, что означает, что дальнейшие боссы будут давать меньше очков.

Кролик нашел в игре лазейку. В любой момент времени он может сбросить прохождение игры и начать новое. Это сбросит текущее значение комбо-бонуса в $$$0$$$, но все побежденные боссы останутся побежденными. Кроме того, текущий счет тоже сохраняется и не сбрасывается в ноль после этой операции. Эта лазейка может быть использована не более $$$k$$$ раз. Можно сбрасывать игру после победы над любым количеством боссов, в том числе перед или после всех, также можно сбрасывать игру несколько раз подряд, не побеждая ни одного босса между сбросами.

Помогите кролику определить максимально возможный счет, который он может получить, победив всех $$$n$$$ боссов.

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

В первой строке содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$0 \leq k \leq 5 \cdot 10^5$$$) — количество боссов и максимальное количество сбросов соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$c_1,c_2,\ldots,c_n$$$ ($$$-10^6 \leq c_i \leq 10^6$$$) — влияние на комбо-бонус каждого из $$$n$$$ боссов.

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

Выведите одно целое число — максимальный счет, который кролик может получить, победив всех $$$n$$$ боссов (обратите внимание, это число может быть отрицательным).

Примеры
Входные данные
3 0
1 1 1
Выходные данные
3
Входные данные
5 1
-1 -2 -3 -4 5
Выходные данные
11
Входные данные
13 2
3 1 4 1 5 -9 -2 -6 -5 -3 -5 -8 -9
Выходные данные
71
Примечание

В первом тесте запрещено делать сбросы. Оптимальное решение будет таким.

  • Победить первого босса $$$(+0)$$$. Комбо-бонус становится равным $$$1$$$.
  • Победить второго босса $$$(+1)$$$. Комбо-бонус становится равным $$$2$$$.
  • Победить третьего босса $$$(+2)$$$. Комбо-бонус становится равным $$$3$$$.

Поэтому ответ в первом примере равен $$$0+1+2=3$$$.

Во втором примере можно показать, что оптимальное решение будет таким:

  • Победить пятого босса $$$(+0)$$$. Комбо-бонус становится равным $$$5$$$.
  • Победить первого босса $$$(+5)$$$. Комбо-бонус становится равным $$$4$$$.
  • Победить второго босса $$$(+4)$$$. Комбо-бонус становится равным $$$2$$$.
  • Победить третьего босса $$$(+2)$$$. Комбо-бонус становится равным $$$-1$$$.
  • Сбросить. Комбо-бонус становится равным $$$0$$$.
  • Победить четвертого босса $$$(+0)$$$. Комбо-бонус становится равным $$$-4$$$.

Поэтому ответ будет равен $$$0+5+4+2+0=11$$$.