J. Jaded Jeweler's Journey
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Jasper is a world-renowned jeweler who has just acquired $$$n$$$ rare gemstones. Each gemstone has a certain luster value $$$a_i$$$. To showcase them in his gallery, Jasper needs to arrange these stones into exactly $$$k$$$ non-empty display cases.

Jasper is a perfectionist. For any display case $$$s$$$ containing $$$m$$$ stones, he defines the Visual Strain $$$f(s)$$$ as the sum of the differences between the maximum and minimum luster seen so far as a visitor walks past the case from left to right. Formally, if the stones are placed in the order $$$s_1, s_2, \dots, s_m$$$, the strain is:

$$$$$$ f(s) = \sum_{i=1}^{m} \left( \max_{1 \le j \le i} \{s_j\} - \min_{1 \le j \le i} \{s_j\} \right) $$$$$$

Jasper knows the order within a case matters. For each case, he will expertly rearrange the stones he is given to ensure the Visual Strain is as small as possible. Let $$$g(s)$$$ be the minimum possible value of $$$f(s)$$$ across all $$$m!$$$ permutations of the stones in $$$s$$$.

Your task is to partition the $$$n$$$ gemstones into exactly $$$k$$$ disjoint non-empty subsequences $$$s_1, s_2, \dots, s_k$$$ such that every gemstone belongs to exactly one subsequence, and the total Visual Strain $$$\sum_{i=1}^{k} g(s_i)$$$ is minimized.

Input

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

Each test case consists of two lines: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — the number of gemstones and the number of display cases. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the luster values of the gemstones.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$2.5 \cdot 10^7$$$.

Output

For each test case, print a single integer representing the minimum possible total Visual Strain.

Example
Input
3
5 2
1 10 5 8 3
3 1
1 5 10
11 1
4 4 4 4 4 6 6 3 3 3 3
Output
8
13
10
Note

In the first test case, an optimal partition is $$$s_1 = \{1, 3, 5\}$$$ and $$$s_2 = \{8, 10\}$$$.

  • For $$$s_1$$$, the optimal permutation is $$$(3, 1, 5)$$$. The prefix ranges are $$$[3,3]$$$, $$$[1,3]$$$, and $$$[1,5]$$$, giving a strain of $$$(3-3) + (3-1) + (5-1) = 0 + 2 + 4 = 6$$$.
  • For $$$s_2$$$, the optimal permutation is $$$(8, 10)$$$, giving a strain of $$$(8-8) + (10-8) = 2$$$.
  • Total strain: $$$6 + 2 = 8$$$.

In the second test case, all stones must be in one case $$$\{1, 5, 10\}$$$. The optimal permutation is $$$(5, 1, 10)$$$, yielding $$$(5-5) + (5-1) + (10-1) = 0 + 4 + 9 = 13$$$.

In the third test case, there is only one case ($$$k=1$$$) containing five $$$4$$$s, two $$$6$$$s, and four $$$3$$$s. An optimal permutation is $$$(4, 4, 4, 4, 4, 3, 3, 3, 3, 6, 6)$$$.

  • For the first $$$5$$$ elements ($$$4$$$s), the range is $$$[4, 4]$$$, so the strain is $$$5 \cdot 0 = 0$$$.
  • For the next $$$4$$$ elements ($$$3$$$s), the range expands to $$$[3, 4]$$$, adding $$$4 \cdot (4-3) = 4$$$.
  • For the final $$$2$$$ elements ($$$6$$$s), the range expands to $$$[3, 6]$$$, adding $$$2 \cdot (6-3) = 6$$$.
  • The total minimum visual strain is $$$0 + 4 + 6 = 10$$$.