F. 排队
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

伍六七的理发店里突然来了一群 Capoo！但由于已经是下班时间所以 Capoo 们打算第二天再来。

然而，Capoo 们的起床时间有所不同，于是一番商量后，领头的 Capoo 递来了一张预约表，上面写着第 $$$i$$$ 只 Capoo 的预约时间为 $$$t_i$$$。

但是 Capoo 实在是太多了！为了应对如此多的 Capoo，伍六七不得不找到隔壁的杀马特协商，经过研究后他们决定将这 $$$n$$$ 只排队的 Capoo 从中间划分成连续的两部分（可以为空）$$$\dagger$$$，前半部分由杀马特负责，后半部分由伍六七负责，而他们给 Capoo 理发所需时间都为 $$$k$$$，这意味着，若伍六七/杀马特在第 $$$l$$$ 秒开始给 Capoo 理发，则他在 $$$[l,l+k)$$$ 这段时间内都在给这只 Capoo 理发而不能给其他 Capoo 理发。如果某只 Capoo 来的时候若伍六七/杀马特正在给其它 Capoo 理发，那它就只好排队等候直到轮到它理发。

现在问题是如何确定一个最佳的划分，使得所有 Capoo 的等待时间之和最小——这里对于第 $$$i$$$ 只 Capoo，它的等待时间为 $$$(\text{开始理发时间} - \text{到达时间})$$$。

为了集思广益，塑料把这道题丢到了校赛里，并期待你给出一个最佳的划分，而你只需要输出最小的等待时间之和，这样塑料就不需要写 spj 了 OuO

$$$\dagger$$$ 对于队列 $$$[1,2,3,4,5]$$$，可能的划分为：$$$[1,2]$$$ 和 $$$[3,4,5]$$$、$$$[1,2,3,4,5]$$$ 和 $$$[]$$$；不允许的划分：$$$[1,2,4]$$$ 和 $$$[3,5]$$$，因为元素在原数组中不连续。

Input

本题有多组测试数据。

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 2\times 10^4$$$)，表示有 $$$T$$$ 组样例；

接下来对于每组测试样例：

第一行输入两个正整数 $$$n$$$ ($$$1 \leq n\leq 2 \times 10^5$$$) 和 $$$k$$$ ($$$1 \leq k \leq 10^8$$$)，表示 Capoo 的数量和给某只 Capoo 理发所需时间；

第二行输入 $$$n$$$ 个正整数，其中第 $$$i$$$ 个数表示第 $$$i$$$ 只 Capoo 的预约时间 $$$t_i$$$ ($$$1 \leq t_i \leq 10^8$$$)。

保证所有测试样例的 $$$n$$$ 之和不超过 $$$5 \times 10^5$$$。

Output

对于每组测试样例，输出一行一个正整数 $$$w$$$，表示最小等待时间之和。

Examples
Input
3
3 5
1 1 4
5 4
4 1 7 2 6
6 3
1 1 1 1 1 1
Output
2
3
18
Input
2
6 57
80 60 27 22 71 66
9 69
13 18 16 32 44 27 24 15 12
Output
163
1015
Note

对于第一个样例组的第二组测试样例：

如果选择将序列划分为 $$$[1,4)$$$ 和 $$$[4,5]$$$，则等待时间计算如下：

对于杀马特负责的部分，

$$$t=1$$$ 时编号为 $$$2$$$ 的 Capoo 到达，杀马特开始为其理发；

$$$t=4$$$ 时编号为 $$$1$$$ 的 Capoo 到达，但此时杀马特还在为编号为 $$$2$$$ 的 Capoo 理发，需要排队等到 $$$t=5$$$ 时才轮到它；

$$$t=7$$$ 时编号为 $$$3$$$ 的 Capoo 到达，但此时杀马特还在为编号为 $$$1$$$ 的 Capoo 理发，需要排队等到 $$$t=9$$$ 时才轮到它。

故这三只 Capoo 的等待时间之和为 $$$1+2=3$$$，而伍六七负责的两只 Capoo 均不需要等待，故总等待时间为 $$$3+0=3$$$。

可以证明不存在更优的方案。