雷顿女士与分队（hard version）

题号：NC200005
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\textbf{请注意，easy version与hard version的区别仅在于题目中n和k的范围不同。}$

卡特莉接到来自某程序设计竞赛集训队的邀请,来为他们进行分队规划。

现在集训队共有n名选手，选手们的实力可以用一个整数来表示。

当若干个选手被分到了一队，队内会因为实力的不平衡而产生矛盾。

具体的来说，我们用矛盾因数来量化矛盾的大小，一个队的矛盾因数为队内成员实力的最大值减去最小值。

现在我们需要将n名选手恰好分为 $\left \lfloor \frac{n}{k}\right \rfloor$ 队( $\left \lfloor \right \rfloor$ 为向下取整符号)，并且每个队最少有k个人。

请你帮卡特莉回答一下他们分出的队的矛盾因数总和最小是多少。

输入描述:

第一行输入一个T(1<=T<=10)表示数据组数。

接下来T组数据。

然后输入n，k(1<=n<=100000,1<=k<=n)。

然后接下来一行输入n个数字，第i个数字表示标号为i的选手的实力()。

输出描述:

对于每组数据，请输出一个数字表示答案。

请注意，行末不要输出多余空格。

示例1

输入

复制

6
5 1
1 2 3 1 1
5 2
1 2 3 1 1
5 3
1 2 3 1 1
5 4
1 2 3 1 1
5 5
1 2 3 1 1
9 3
1 1 2 2 1 10 10 10 10

输出

复制

备注:

样例1可以为:(1-1)+(2-2)+(3-3)+(1-1)+(1-1)=0


样例2可以为:(1-1)+(3-2)=1


样例3可以为:(3-1)=2