3129: Playful Worker

$Alice$ is a well-known builder who has designed many well-known buildings, such as the rainbow tower. This time, someone asks her to build a strange building, which only needs stones. So  $Alice$ bought a batch of stones. Now, there are n heaps of stones in front of   $Alice$. $Alice$ can start work only after she combines these n heaps of stones into a heap. $ Alice$ has prepared a machine to merge the stones. However, there is something wrong with this machine. It takes at least two heaps at a time and at most $m$ heaps of stones to merge. The cost of each merging is the number of stones. Alice wants to know the minimum cost of merging $n$ heaps of stones into one heap of stones.

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \leq T \leq 10^4$). Description of the test cases follows.

The first line of each test case contains Two integers $n$ ($2 \leq n \leq 10^6$)  and  $m$ ($2 \leq m \leq n$)  — The number of stones piled up and the maximum number of gravel piles to merge at one time.

Each of the next  line contains $n$ positive integers $a_{i}$ ($1 \leq a_{i} \leq 10^6$), describing the $i$-th segment.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, print a single integer $k$, minimum cost of merging stones.

3
5 2
1 2 3 4 5
5 3
1 2 3 4 5
5 4
1 2 3 4 5

33
21
18