当前没有测试数据。

C. Trip Shopping

题目描述

Ali 和 Bahamin 决定在伊朗美丽的南部海岸度过暑假。他们还同意在旅行中购物——但他们没有设定固定预算，而是决定通过玩一个游戏来确定花费金额。

游戏在两个均包含 $n$ 个整数的数组 $a$ 和 $b$ 上进行。

游戏将持续 $k$ 轮。每一轮的规则如下：

1. 首先，Ali 选择两个索引 $i$ 和 $j$（满足 $1 \leq i < j \leq n$）；
2. 然后，Bahamin 可以将四个整数 $a_i$、$a_j$、$b_i$、$b_j$ 任意重新排列。注意：Bahamin 可以在两个数组之间交换数字，也可以保持两个数组不变。

所有 $k$ 轮结束后，游戏的价值定义为 $v = \sum\limits_{i=1}^{n} |a_i - b_i|$。Ali 和 Bahamin 将恰好花费 $v$ 枚硬币。

然而，他们的目标截然不同：

• Ali 希望花费尽可能少，即最小化 $v$；
• Bahamin 希望花费尽可能多，即最大化 $v$。

如果两人都采取最优策略，请你求出他们最终的花费金额。

输入格式

输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \leq t \leq 10^4$）。

每组测试用例的输入格式如下：

1. 第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq n$）—— 数组 $a$ 和 $b$ 的长度，以及游戏的轮数；
2. 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）—— 数组 $a$ 的元素；
3. 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$）—— 数组 $b$ 的元素。

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

输出格式

对于每组测试用例，输出一个整数——两人都采取最优策略时的最终花费金额。

输入输出样例

输入

样例

输入

5
2 1
1 7
3 5
3 2
1 5 3

输出

6 2 4
5 4
1 16 10 10 16
3 2 2 15 15
4 1
23 1 18 4
19 2 10 3
10 10
4 3 2 100 4 1 2 4 5 5
1 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]$，此时游戏价值为 $|5 - 3| + |1 - 7| = 8$。可以证明这是 Bahamin 能达到的最大可能值——其他排列（如 $a = [5, 7]$、$b = [1, 3]$）也可行，但不会得到更大的价值。

在第二个测试用例中，无论 Ali 选择哪些索引，Bahamin 的最优策略都是保持两个数组不变。此时游戏价值为 $|1 - 6| + |5 - 2| + |3 - 4| = 9$。