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

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

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

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

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

对于队列 ，可能的划分为： 和 、 和 ；不允许的划分： 和 ，因为元素在原数组中不连续。

输入描述:

本题有多组测试数据。

第一行输入一个正整数  ()，表示有  组样例；

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

第一行输入两个正整数  () 和  ()，表示 Capoo 的数量和给某只 Capoo 理发所需时间；

第二行输入  个正整数，其中第  个数表示第  只 Capoo 的预约时间  ()。

保证所有测试样例的  之和不超过 。

输出描述:

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

3
3 5
1 1 4
5 4
4 1 7 2 6
6 3
1 1 1 1 1 1

2
3
18

2
6 57
80 60 27 22 71 66
9 69
13 18 16 32 44 27 24 15 12

163
1015

备注:

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

如果选择将序列划分为  和 ，则等待时间计算如下：

对于杀马特负责的部分，

 时编号为  的 Capoo 到达，杀马特开始为其理发；

 时编号为  的 Capoo 到达，但此时杀马特还在为编号为  的 Capoo 理发，需要排队等到  时才轮到它；

 时编号为  的 Capoo 到达，但此时杀马特还在为编号为  的 Capoo 理发，需要排队等到  时才轮到它。

故这三只 Capoo 的等待时间之和为 ，而伍六七负责的两只 Capoo 均不需要等待，故总等待时间为 。

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