D. Ловушки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, в мире всегда есть недобросовестные люди. К сожалению, иногда такие люди делают ревью, и самый умный человек на земле (естественно, Тётя Люсине) придумала хитрейший способ с ними бороться: ханипоты! Но Тётя Люсине пошла ещё дальше: она замаскировала все ханипоты под «ловушки»! Теперь вам, как самому лучшему ревьюверу, нужно через них пробраться.

Вам нужно преодолеть $$$n$$$ ловушек, пронумерованных от $$$1$$$ до $$$n$$$. Вы будете проходить через ловушки по очереди. $$$i$$$-я ловушка наносит вам $$$a_i$$$ базового урона.

Вместо того, чтобы проходить через ловушку, вы можете перепрыгнуть ее. Всего вы можете перепрыгнуть не более $$$k$$$ ловушек. В случае, если вы перепрыгиваете ловушку, вы не получаете от неё урона. Однако если вы перепрыгиваете какую-то ловушку, то это увеличивает урон каждой следующей ловушки на $$$1$$$ (это бонусный урон).

Обратите внимание, что если вы перепрыгиваете ловушку, то вы не получаете от неё урона (ни базовый, ни бонусный), а что также бонусные уроны от прыжков складываются. Например, если вы проходите через $$$i$$$-ю ловушку с базовым уроном $$$a_i$$$, а до этого вы перепрыгнули $$$3$$$ другие ловушки, то вы получите от неё $$$(a_i + 3)$$$ урона.

Определите, какое минимальный суммарный урон вы можете получить, если разрешается перепрыгнуть не больше $$$k$$$ любых ловушек.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$) — количество ловушек и максимальное количество ловушек, которые вы можете перепрыгнуть.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — базовые уроны ловушек.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно число — минимальный суммарный урон, который можно получить, если можно перепрыгнуть не больше $$$k$$$ любых ловушек.

Пример
Входные данные
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
Примечание

В первом наборе входных данных можно перепрыгнуть все ловушки и получить $$$0$$$ урона.

Во втором наборе входных данных есть $$$5$$$ способов перепрыгнуть ловушки:

  1. Не перепрыгивать никакие ловушки.

    Суммарный урон: $$$5 + 10 + 11 + 5 = 31$$$.

  2. Перепрыгнуть $$$1$$$-ю ловушку.

    Суммарный урон: $$$\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$$$.

  3. Перепрыгнуть $$$2$$$-ю ловушку.

    Суммарный урон: $$$5 + \underline{0} + (11 + 1) + (5 + 1) = 23$$$.

  4. Перепрыгнуть $$$3$$$-ю ловушку.

    Суммарный урон: $$$5 + 10 + \underline{0} + (5 + 1) = 21$$$.

  5. Перепрыгнуть $$$4$$$-ю ловушку.

    Суммарный урон: $$$5 + 10 + 11 + \underline{0} = 26$$$.

Чтобы получить минимальный урон, необходимо перепрыгнуть $$$3$$$-ю ловушку, тогда ответ будет $$$21$$$.

В третьем наборе входных данных оптимально перепрыгнуть через ловушки с номерами $$$1$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$7$$$:

Суммарный урон: $$$0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9$$$.