Migrated from Lutece 2971 天才魔导器

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

这天，艾妮丝菲亚和尤菲莉亚在一起研究讨论完魔法工学后，艾妮丝菲亚快速绘制出了一张魔法构件图，这个构件图是由 $n$ 个魔法传输节点构成，每个节点有个魔力值 $v_i$ 和魔力类型 $t_i$，这些魔法传输节点可以互相通过魔力通道连接，如果两个连接的节点 $i, j$ 魔力类型不同，则该通道的传输效率为 $|v_i - v_j|$，如果相同，则传输效率为 $|v_i + v_j|$。

由于是天才皇女，艾妮丝菲亚的魔法构件图非常精妙，所对应生产的魔导器也非常强大，尤菲莉亚也想和她一样创造出强大魔导器。为了充分利用资源，她想将这 $n$ 个魔法传输节点用魔法通道全部恰好连通，在所用魔法通道数量尽量少的前提下，使得总传输效率（所有魔法通道传输效率之和）最大。但尤菲莉亚怎么都无法画出最完美的魔法构件图，所以聪明的你能帮帮她吗？

Input

第一行一个整数 $T (1\leq T\leq 100)$ 表示尤菲莉亚需要画 $T$ 个魔导器的魔法构件图。

对于每一个魔导器的魔法构件图，输入描述如下： 第一行两个数字 $n,m\ (1\leq n,m\leq 500000)$ 表示有 $n$ 个魔力传输节点和 $m$ 种魔力。 第二行 $n$ 个数字，第 $i$ 个整数表示第 $i$ 个魔法传输节点的魔力值 $v_i\ (1\leq v_i\leq 10^9)$。 第三行 $n$ 个数字，第 $i$ 个整数表示第 $i$ 个魔法传输节点的魔力类型 $t_i\ (0\leq t_i< m)$ 。

Output

输出一个整数表示最大总传输效率。

Samples

2
4 2
1 2 3 4
0 1 0 1
6 3
1 1 4 5 1 4
0 1 2 0 1 2

13
25

Constraints

保证 $T$ 个魔导器的魔法构件图满足 $\sum n\leq 500000$。

Note

对于第一个样例，一号节点连接三号四号，二号节点连接四号，此时效率总和最大化，为 $|1+3|+|1-4|+|2+4|=13$。

Resources

2023 UESTC ICPC Training for Graph