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\)。