Как известно, в мире всегда есть недобросовестные люди. К сожалению, иногда такие люди делают ревью, и самый умный человек на земле (естественно, Тётя Люсине) придумала хитрейший способ с ними бороться: ханипоты! Но Тётя Люсине пошла ещё дальше: она замаскировала все ханипоты под «ловушки»! Теперь вам, как самому лучшему ревьюверу, нужно через них пробраться.
Вам нужно преодолеть \(n\) ловушек, пронумерованных от \(1\) до \(n\). Вы будете проходить через ловушки по очереди. \(i\)-я ловушка наносит вам \(a_i\) базового урона.
Вместо того, чтобы проходить через ловушку, вы можете перепрыгнуть ее. Всего вы можете перепрыгнуть не более \(k\) ловушек. В случае, если вы перепрыгиваете ловушку, вы не получаете от неё урона. Однако если вы перепрыгиваете какую-то ловушку, то это увеличивает урон каждой следующей ловушки на \(1\) (это бонусный урон).
Обратите внимание, что если вы перепрыгиваете ловушку, то вы не получаете от неё урона (ни базовый, ни бонусный), а что также бонусные уроны от прыжков складываются. Например, если вы проходите через \(i\)-ю ловушку с базовым уроном \(a_i\), а до этого вы перепрыгнули \(3\) другие ловушки, то вы получите от неё \((a_i + 3)\) урона.
Определите, какое минимальный суммарный урон вы можете получить, если разрешается перепрыгнуть не больше \(k\) любых ловушек.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальный суммарный урон, который можно получить, если можно перепрыгнуть не больше \(k\) любых ловушек.
Примечание
В первом наборе входных данных можно перепрыгнуть все ловушки и получить \(0\) урона.
Во втором наборе входных данных есть \(5\) способов перепрыгнуть ловушки:
- Не перепрыгивать никакие ловушки.
Суммарный урон: \(5 + 10 + 11 + 5 = 31\).
- Перепрыгнуть \(1\)-ю ловушку.
Суммарный урон: \(\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29\).
- Перепрыгнуть \(2\)-ю ловушку.
Суммарный урон: \(5 + \underline{0} + (11 + 1) + (5 + 1) = 23\).
- Перепрыгнуть \(3\)-ю ловушку.
Суммарный урон: \(5 + 10 + \underline{0} + (5 + 1) = 21\).
- Перепрыгнуть \(4\)-ю ловушку.
Суммарный урон: \(5 + 10 + 11 + \underline{0} = 26\).
Чтобы получить минимальный урон, необходимо перепрыгнуть \(3\)-ю ловушку, тогда ответ будет \(21\).
В третьем наборе входных данных оптимально перепрыгнуть через ловушки с номерами \(1\), \(3\), \(4\), \(5\), \(7\):
Суммарный урон: \(0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 4
8 7 1 4
4 1
5 10 11 5
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
1 1
7
|
0
21
9
6
0
|