卡尔斯对他的村庄的狭隘思维感到厌倦和不满,因为他们满足于留在原地,而不是试图成为完美的生命形式。作为一名顶尖的发明家,卡尔斯希望增强自己的身体,成为完美的生命体。不幸的是,$$$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$$$ 的权力。
Kars 想要将村民准确地分成 $$$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)$$$ 最小。帮助 Kars 找到 $$$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)$$$ - 每个村民的怀疑。
输出
对于每个测试用例,输出一个整数 - 所有组 i 的幂总和的最小可能值。 e. $$$f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$ 的最小可能值。
示例
输入 #1
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
输出 #1
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$$$。