Migrated from Lutece 3173 牌佬的自我素养

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

fix： 关于每一轮的游戏过程，可以理解为 lg114 先打出一张牌，lg514 看到之后再选择打哪张 lg514 可以选择将牌删光以获得胜利

g114 找 lg514 打牌，游戏规则如下：

两人先各自随机抓取 $n$ 张牌，双方都可以看到对方的手牌。总共进行 $n$ 轮游戏，每轮游戏双方各打出一张牌，之后打出的牌放入弃牌堆不能再使用。当一张牌上的数字严格大于另一张牌时，我们称这张牌更强，只有当某个人每一轮打出的牌都要比另一个人打出的牌更强时，他才能取得游戏的胜利。

举例说明： lg114 有数值为 $4, 2, 3, 1$ 的共计 4 张牌，lg514 有数值为 $2, 6, 4, 5$ 的共计 4 张牌，那么 lg514 获胜： lg114 使用值为 $4$ 的牌时， lg514 使用值为 $6$ 的牌; lg114 使用值为 $2$ 的牌时， lg514 使用值为 $4$ 的牌; lg114 使用值为 $3$ 的牌时， lg514 使用值为 $5$ 的牌; lg114 使用值为 $1$ 的牌时， lg514 使用值为 $2$ 的牌;

这本来是个比较公平的游戏，但由于 lg114 的打牌技术不好，最后 lg514 取得了所有的胜利，lg114 破防不干了，他要求 lg514 将游戏规则修改的对他更为有利，否则就走人不陪他玩了。经过一番友好(?)交流之后，两个人最终增添了如下游戏规则：

• lg114 可以将抓到的第一张手牌修改为 $1$ 到 $m$ 的任意一个值。
• lg514 可以选择给 lg114 $k$ 元钱，然后从两个人的手牌中分别任意选 $k$ 张删掉。

然而，大佬 lg514 仍然有信心从 lg114 手中拿下绝对胜利！

以上内容为 lg 同学五一期间闲的没事想出来的小剧场，不过他觉得这个问题可以出到队内赛里。

请你算出 lg114 将 抽到的第一张牌的值修改为 $1$ 到 $m$ 的每一个数时， lg514 想要赢下每一轮游戏要给的钱的最少值之和。

Input

第一行一个数 $t$ ，表示共有 $t$ 个测试样例。 每组测试样例有三行，第一行两个数 $n, m$，为两人的牌数，以及 $a_1$ 可以变化的范围。 第二行 $n-1$ 个数 $a_2, a_3, ......, a_n$ ，表示 lg114 抽到的其他牌。 第三行 $n$ 个数 $b_1, b_2, ......, b_n$ ，表示 lg514 抽到的牌。

Output

共 $q$ 行，表示每个测试样例的答案。

Samples

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

2
15
4

Constraints

$1 \leq t \leq 10^4$，$2 \leq n \leq 10^5$，$1 \leq m \leq 10^9$ 对于任意 $i$ 满足 $2 \leq i \leq n$，有 $1 \leq a_i \leq10^9$ 对于任意 $i$ 满足 $1 \leq i \leq n$，有 $1 \leq b_i \leq10^9$ 保证 $n$ 的总和不超过 $10^5$

Note

对于第一组样例： $a_1$=1 时 lg114 的牌为$[1,1]$，答案为0，不需要操作就能满足条件。 $a_1$=2 时 lg114 的牌为$[2,1]$，答案为0，不需要操作就能满足条件。 $a_1$=3 时 lg114 的牌为$[3,1]$，答案为1，去掉 lg114 中的数值为 3 的牌与 lg514 中的数值为 2 的牌即满足条件。注意需要满足严格大于的条件。 $a_1$=4 时 lg114 的牌为$[4,1]$，答案为1，去掉 lg114 中的数值为 4 的牌与 lg514 中的数值为 2 的牌即满足条件。 答案总和为$0+0+1+1=2$。 冷芝士：$lg114514\approx5.1$，所以大家五一快乐（？）。