阿里和巴哈明决定去伊朗美丽的南部海岸度过暑假。他们还同意在旅途中进行一些购物,但他们没有设定固定预算,而是决定通过玩游戏来确定要花多少钱。
游戏在两个数组 $$$a$$$ 和 $$$b$$$ 上进行,每个数组包含 $$$n$$$ 整数。
游戏将持续 $$$k$$$ 轮。在一轮中:
- 首先,阿里选择两个索引$$$i$$$和$$$j$$$ ($$$1 \leq i \lt j \leq n$$$);
- 然后,Bahamin 重新排列四个整数 $$$a_i$$$、$$$a_j$$$、$$$b_i$$$ 和 $$$b_j$$$ 任意。请注意,Bahamin 可以在两个数组之间交换数字。他还可以保持两个阵法不变。
在所有 $$$k$$$ 轮之后, 游戏的 值 路径的 定义为$$$v=\sum\limits_{i=1}^{n} |a_i-b_i|$$$。阿里和巴哈明在旅途中将花费恰好 $$$v$$$ 硬币。
然而,他们的目标却截然不同:
- 阿里希望花尽可能少的钱,即最小化$$$v$$$;
- 巴哈明想要尽可能多地支出,即最大化 $$$v$$$。
你必须找到如果阿里和巴哈明都发挥最佳状态,他们最终会花费的金币数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) - $$$a$$$ 和 $$$b$$$ 的长度,以及轮数。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — $$$a$$$ 的元素。
第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — $$$b$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 如果阿里和巴哈明都发挥最佳状态,他们将花费的最终硬币数量。
示例
输入复制
52 11 73 53 21 5 36 2 45 41 16 10 10 163 2 2 15 154 123 1 18 419 2 10 310 104 3 2 100 4 1 2 4 5 51 200 4 5 6 1 10 2 3 4
输出复制
8 9 30 16 312
注意
在第一个测试用例中,Ali只能选择$$$(i, j) = (1, 2)$$$,而Bahamin可以重新排列所有四个数字。因此,他可以分配 $$$a = [5, 1]$$$ 和 $$$b = [3, 7]$$$。还有 游戏的 值 路径的 将为$$$v=|5 - 3| + |1 - 7| = 8$$$。可以证明这是最大可能的 值 路径的 可到达巴哈明 - 其他安排如 $$$a = [5, 7],\space b = [1, 3]$$$ 也是可能的,但它们没有更大的值。
在第二个测试用例中,Bahamin 的最佳策略是保持两个数组不变,无论 Ali 选择什么索引。还有 游戏的 值 路径的 将为$$$v=|1 - 6| + |5 - 2| + |3 - 4| = 9$$$。