← 返回题目列表

Codeforces · 2127/C

C. 旅行购物

中文机器翻译题面 查看原题

阿里和巴哈明决定去伊朗美丽的南部海岸度过暑假。他们还同意在旅途中进行一些购物,但他们没有设定固定预算,而是决定通过玩游戏来确定要花多少钱。

游戏在两个数组 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - 如果阿里和巴哈明都发挥最佳状态,他们将花费的最终硬币数量。

示例

输入
复制

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]$$$。还有 游戏的 值 路径的 将为$$$v=|5 - 3| + |1 - 7| = 8$$$。可以证明这是最大可能的 值 路径的 可到达巴哈明 - 其他安排如 $$$a = [5, 7],\space b = [1, 3]$$$ 也是可能的,但它们没有更大的值。

在第二个测试用例中,Bahamin 的最佳策略是保持两个数组不变,无论 Ali 选择什么索引。还有 游戏的 值 路径的 将为$$$v=|1 - 6| + |5 - 2| + |3 - 4| = 9$$$。