Problem Description

事实上，真实的做法是将学长的实验报告 copy 后，修改名字，没了。

你是一名深陷期末月的大学生。在《算法设计与分析》这门课上，教授要求每人提交一份实验报告。

幸运的是，你从往届学长那里搞到了 $n$ 份现成的报告，第 $i$ 份有 $a_i$ 页，直接交会被查重系统当场逮捕。你的策略是：每次选取至多 $k$ 份报告，把它们摞在一起，封面写上自己的名字——这就“合成”了一份新报告。每次合成的代价为这些报告的总页数。合成后得到一份新报告，其页数为合成前的页数之和。

除了实验报告，你还有很多事情要忙，比如说：谈恋爱、和朋友吃饭、游玩舞萌等等，所以你希望合成最终实验报告的总代价最小，请求出这个总代价。

Input Format

第一行一个整数 $T$（$1 \le T \le 1000$），表示测试数据组数。

每组数据：

第一行两个整数 $n, k$（$2 \le k \le n \le 2 \times 10^5$）。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每份报告的页数。

保证所有测试数据的 $\sum n \le 2 \times 10^5$。

Output Format

输出 $T$行，每行输出一行一个整数，表示最小总代价。

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

21
20

Hint

对于第一组测试用例：

第 $1$ 次，合并 $3$ 份报告，代价分别为$\{1,2,3\}$，代价 $6$，得到一份页数为 $6$ 的报告。

第 $2$ 次，合并 $3$ 份报告，代价分别为 $\{4,5,6\}$，代价 $15$，得到一份页数为 $15$ 的报告。

总代价 $6 + 15 = 21$。