C. Минимизация суммы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан целочисленный массив $$$a$$$ размера $$$n$$$.

Вы можете выполнить следующую операцию: выбрать элемент массива и заменить его значением любого из его соседей.

Например, если $$$a=[3, 1, 2]$$$, вы можете получить один из массивов $$$[3, 3, 2]$$$, $$$[3, 2, 2]$$$ и $$$[1, 1, 2]$$$ за одну операцию, но не $$$[2, 1, 2$$$] и $$$[3, 4, 2]$$$.

Ваша задача — посчитать минимально возможную сумму массива, если вы можете выполнить вышеописанную операцию не более $$$k$$$ раз.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$0 \le k \le 10$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
3 1
3 1 2
1 3
5
4 2
2 2 1 3
6 3
4 1 2 2 4 3
Выходные данные
4
5
5
10
Примечание

В первом примере одна из возможных последовательностей операций: $$$[3, 1, 2] \rightarrow [1, 1, 2$$$].

Во втором примере не нужно применять операцию.

В третьем примере одна из возможных последовательностей операций: $$$[2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1]$$$.

В четвертом примере одна из возможных последовательностей операций: $$$[4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 3]$$$.