CF2127C.Trip Shopping

Ali 和 Bahamin 决定在伊朗美丽的南部海岸度过他们的暑假。他们还决定在旅行期间购物——但他们没有设定固定的预算，而是决定通过玩一个游戏来决定他们会花多少钱。

这个游戏在两个数组 $a$ 和 $b$ 上进行，每个数组包含 $n$ 个整数。

游戏将持续 $k$ 轮。在每一轮中：

• 首先，Ali 选择两个下标 $i$ 和 $j$（$1 \leq i < j \leq n$）；
• 然后，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$。

如果 Ali 和 Bahamin 都采取最优策略，你需要求出他们最终会花费多少硬币。

每个测试用例包含多组数据。第一行包含测试用例数 $t$（$1 \leq t \leq 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$。

对于每组测试用例，输出一个整数——如果 Ali 和 Bahamin 都采取最优策略，他们最终会花费多少硬币。

在第一个测试用例中，Ali 只能选择 $(i, j) = (1, 2)$，Bahamin 可以任意重排这四个数字。因此，他可以将 $a = [5, 1]$，$b = [3, 7]$。此时游戏的值为 $v = |5 - 3| + |1 - 7| = 8$。可以证明，这就是 Bahamin 能达到的最大值——其他排列如 $a = [5, 7],\ b = [1, 3]$ 也可以，但不会得到更大的值。

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

由 ChatGPT 4.1 翻译