The Man who became a God

链接：https://codeforces.com/contest/1847/problem/A
来源：codeforces

时间限制：1 seconds
空间限制：256 megabytes

题目描述

卡尔斯对他的村庄的狭隘心态感到厌倦和不满，因为他们只满足于呆在原地，没有努力成为完美的生命体。作为一个顶级的发明家，卡尔斯希望增强自己的身体，成为完美的生命体。不幸的是，$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≤k≤n≤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$。