A. Человек, ставший Богом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карс возмущен узким мышлением жителей своей деревни, поскольку они довольствуются тем, что стоят на месте, и не пытаются стать совершенной формой жизни. Будучи первоклассным изобретателем, Карс хочет усовершенствовать свое тело и стать совершенной формой жизни. К сожалению, $$$n$$$ жителей деревни с подозрением относятся к его идеям. $$$i$$$-й житель деревни подозревает Карса на $$$a_i$$$. По отдельности каждый житель деревни боится Карса, поэтому они объединяются в группы, чтобы стать сильнее.

Силу группы сельчан от $$$l$$$ до $$$r$$$ можно определить как $$$f(l,r)$$$, где $$$$$$f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|.$$$$$$ Здесь $$$|x-y|$$$ — модуль числа $$$x-y$$$. Группа с одним жителем имеет силу $$$0$$$.

Карс хочет разбить жителей деревни на ровно $$$k$$$ подряд идущих групп так, чтобы сумма их сил была минимальна. Формально, он должен найти $$$k - 1$$$ положительных целых чисел $$$1 \le r_1 < r_2 < \ldots < r_{k - 1} < n$$$ такие, что $$$f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$ минимально. Помогите Карсу найти минимальное значение $$$f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$.

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

Первая строка содержит одно целое число $$$t$$$ $$$(1 \leq t \leq 100)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n,k$$$ $$$(1 \leq k \leq n \leq 100)$$$ — количество жителей деревни и количество групп, на которые они должны быть разбиты.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых $$$a_1,a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 500)$$$ — подозрение каждого из жителей деревни.

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

Для каждого набора входных данных выведите одно целое число — минимально возможное значение суммы сил всех групп, т. е. минимально возможное значение $$$f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$.

Пример
Входные данные
3
4 2
1 3 5 2
6 3
1 9 12 4 7 2
12 8
1 9 8 2 3 3 1 8 7 7 9 2
Выходные данные
4
11
2
Примечание

В первом наборе входных данных сгруппируем жителей деревни с подозрениями $$$(1,3,5,2)$$$ в $$$(1,3,5)$$$ и $$$(2)$$$. Таким образом, $$$f(1,3) + f(4,4) = (|1 - 3| + |3 - 5|) + 0 = 4 + 0 = 4$$$.

Во втором наборе входных данных мы сгруппируем жителей деревни с подозрениями $$$(1,9,12,4,7,2)$$$ в $$$(1),(9,12),(4,7,2)$$$. Итак, $$$f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11$$$.