Задан целочисленный массив $$$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$$$ раз.
43 13 1 21 354 22 2 1 36 34 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]$$$.
Название |
---|