CF1847A.The Man who became a God

Kars is tired and resentful of the narrow mindset of his village since they are content with staying where they are and are not trying to become the perfect life form. Being a top-notch inventor, Kars wishes to enhance his body and become the perfect life form. Unfortunately, $n$ of the villagers have become suspicious of his ideas. The $i$-th villager has a suspicion of $a_i$ on him. Individually each villager is scared of Kars, so they form into groups to be more powerful.

The power of the group of villagers from $l$ to $r$ be defined as $f(l,r)$ where

$$f(l,r) = |a\_l - a\_{l+1}| + |a\_{l + 1} - a\_{l + 2}| + \\ldots + |a\_{r-1} - a\_r|.$$

Here $|x-y|$ is the absolute value of $x-y$. A group with only one villager has a power of $0$.

Kars wants to break the villagers into exactly $k$ contiguous subgroups so that the sum of their power is minimized. Formally, he must find $k - 1$ positive integers $1 \le r_1 \lt r_2 \lt \ldots \lt r_{k - 1} \lt n$ such that $f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$ is minimised. Help Kars in finding the minimum value of $f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$.

卡尔斯因村庄居民狭隘的思想而感到疲惫与愤懑，因为他们满足于现状，不愿努力成为完美的生命体。作为一名顶尖的发明家，卡尔斯渴望强化自身，从而进化为完美的生命体。不幸的是，有 $n$ 名村民开始怀疑他的想法。其中第 $i$ 位村民对他的怀疑值为 $a_i$。由于每位村民 individually 都害怕卡尔斯，他们便结成群体以增强力量。

定义从第 $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 \lt r_2 \lt \ldots \lt r_{k - 1} \lt n$，使得

$$f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$

取得最小值。请帮助卡尔斯求出该表达式的最小值。

The first line contains a single integer $t$ $(1 \leq t \leq 100)$ — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n,k$ $(1 \leq k \leq n \leq 100)$ — the number of villagers and the number of groups they must be split into.

The second line of each test case contains $n$ integers $a_1,a_2, \ldots, a_n$ $(1 \leq a_i \leq 500)$ — the suspicion of each of the villagers.

第一行包含一个整数 $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$）——每位村民的嫌疑值。

For each test case, output a single integer — the minimum possible value of sum of power of all the groups i. e. the minimum possible value of $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)$ 的最小可能值。

In the first test case, we will group the villagers with suspicion $(1,3,5,2)$ into $(1,3,5)$ and $(2)$. So, $f(1,3) + f(4,4) = (|1 - 3| + |3 - 5|) + 0 = 4 + 0 = 4$.

In the second test case, we will group the villagers with suspicion $(1,9,12,4,7,2)$ into $(1),(9,12),(4,7,2)$. So, $f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11$.

在第一个测试用例中，我们将嫌疑值为 $(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$。