Кролик играет в игру, в которой есть \(n\) боссов, пронумерованных от \(1\) до \(n\). Боссов можно побеждать в любом порядке. Каждого босса нужно победить ровно один раз. Также в игре присутствует параметр, называемый комбо-бонусом, изначально равный \(0\).
Когда игрок побеждает \(i\)-го босса, ко счету игрока добавляется текущее значение комбо-бонуса, а затем значение комбо-бонуса изменяется на величину \(c_i\). Обратите внимание, что величина \(c_i\) может быть отрицательной, что означает, что дальнейшие боссы будут давать меньше очков.
Кролик нашел в игре лазейку. В любой момент времени он может сбросить прохождение игры и начать новое. Это сбросит текущее значение комбо-бонуса в \(0\), но все побежденные боссы останутся побежденными. Кроме того, текущий счет тоже сохраняется и не сбрасывается в ноль после этой операции. Эта лазейка может быть использована не более \(k\) раз. Можно сбрасывать игру после победы над любым количеством боссов, в том числе перед или после всех, также можно сбрасывать игру несколько раз подряд, не побеждая ни одного босса между сбросами.
Помогите кролику определить максимально возможный счет, который он может получить, победив всех \(n\) боссов.
Выходные данные
Выведите одно целое число — максимальный счет, который кролик может получить, победив всех \(n\) боссов (обратите внимание, это число может быть отрицательным).
Примечание
В первом тесте запрещено делать сбросы. Оптимальное решение будет таким.
- Победить первого босса \((+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\).