#P1847A. The Man who became a God

The Man who became a God

Description

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, nn of the villagers have become suspicious of his ideas. The ii-th villager has a suspicion of aia_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 ll to rr be defined as f(l,r)f(l,r) where

f(l,r)=alal+1+al+1al+2++ar1ar.f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|.

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

Kars wants to break the villagers into exactly kk contiguous subgroups so that the sum of their power is minimized. Formally, he must find k1k - 1 positive integers 1r1<r2<<rk1<n1 \le r_1 < r_2 < \ldots < r_{k - 1} < n such that f(1,r1)+f(r1+1,r2)++f(rk1+1,n)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,r1)+f(r1+1,r2)++f(rk1+1,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 tt (1t100)(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,kn,k (1kn100)(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 nn integers a1,a2,,ana_1,a_2, \ldots, a_n (1ai500)(1 \leq a_i \leq 500) — the suspicion of each of the villagers.

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,r1)+f(r1+1,r2)++f(rk1+1,n)f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n).

Input

The first line contains a single integer tt (1t100)(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,kn,k (1kn100)(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 nn integers a1,a2,,ana_1,a_2, \ldots, a_n (1ai500)(1 \leq a_i \leq 500) — the suspicion of each of the villagers.

Output

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,r1)+f(r1+1,r2)++f(rk1+1,n)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

Note

In the first test case, we will group the villagers with suspicion (1,3,5,2)(1,3,5,2) into (1,3,5)(1,3,5) and (2)(2). So, f(1,3)+f(4,4)=(13+35)+0=4+0=4f(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)(1,9,12,4,7,2) into (1),(9,12),(4,7,2)(1),(9,12),(4,7,2). So, f(1,1)+f(2,3)+f(4,6)=0+3+8=11f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11.