H. Минимизировать стоимость
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для последовательности $$$b$$$ длины $$$m$$$ определим её функцию стоимости $$$f(b)$$$: $$$$$$ f(b) = m \cdot \sum_{i=1}^m b_i.$$$$$$

Вам дана последовательность $$$a$$$ длины $$$n$$$ и целое число $$$k$$$.

Ваша задача состоит в том, чтобы разбить последовательность $$$a$$$ на ровно $$$k$$$ непустых подпоследовательностей$$$^{\text{∗}}$$$ $$$s_1, s_2, \ldots, s_k$$$. Каждый элемент исходной последовательности $$$a$$$ должен принадлежать ровно одной из этих подпоследовательностей.

Найдите минимально возможное значение суммарной стоимости: $$$$$$ \sum_{i=1}^k f(s_i).$$$$$$

$$$^{\text{∗}}$$$Последовательность $$$c$$$ является подпоследовательностью $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$\mathbf{-10^9} \le a_i \le \mathbf{10^9}$$$) — элементы последовательности $$$a$$$.

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

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

Для каждого набора входных данных выведите одно целое число – минимальную сумму стоимостей по всем подпоследовательностям.

Пример
Входные данные
6
3 2
1 3 -2
3 1
1 3 -2
10 4
-4 -6 -8 6 -3 -7 -3 1 6 -5
10 9
1 -2 6 -2 -6 4 3 3 7 -1
20 5
-5 9 -4 10 -2 4 -1 3 5 6 7 9 8 1 0 -6 4 5 8 9
50 26
7 10 10 2 2 1 7 4 4 8 5 8 -10 6 1 4 7 8 0 0 -8 1 1 5 0 0 6 0 7 4 6 0 7 4 -2 0 0 8 1 4 -7 0 6 -9 4 10 8 2 0 9
Выходные данные
1
6
-239
5
131
-404
Примечание

В первом наборе входных данных оптимально разбить на $$$[1,-2]$$$ и $$$[3]$$$. Суммарная стоимость составляет $$$2(1-2)+1(3)=1$$$.

Во втором наборе входных данных есть только одно разбиение с $$$1$$$ подпоследовательностью $$$[1,3,-2]$$$. Счёт равен $$$3(1+3-2)=6$$$.