← 返回题目列表

Codeforces · 1921/D

D. 非常不同的阵列

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

Petya 有一个由 $$$n$$$ 整数组成的数组 $$$a_i$$$。他的兄弟 Vasya 很嫉妒,决定制作自己的 $$$n$$$ 整数数组。

为此,他找到了$$$m$$$个整数$$$b_i$$$ ($$$m\ge n$$$),现在他想选择其中的$$$n$$$个整数,并按一定的顺序排列它们,以获得长度为$$$n$$$的数组$$$c_i$$$。

为了避免与他的兄弟相似,Vasya 想让他的数组与 Petya 的数组尽可能不同。具体来说,他希望总差 $$$D = \sum_{i=1}^{n} |a_i - c_i|$$$ 尽可能大。

帮助 Vasya 找到他可以获得的最大差异 $$$D$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n\le m\le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1\le a_i\le 10^9$$$)。每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_i$$$ ($$$1\le b_i\le 10^9$$$)。

保证在一次测试中,所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 可以获得的最大总差 $$$D$$$。

示例

输入 #1

9
4 6
6 1 2 4
3 5 1 7 2 3
3 4
1 1 1
1 1 1 1
5 5
1 2 3 4 5
1 2 3 4 5
2 6
5 8
8 7 5 8 2 10
2 2
4 1
9 6
4 6
8 10 6 4
3 10 6 1 8 9
3 5
6 5 2
1 7 9 7 2
5 5
9 10 6 3 7
5 9 2 3 9
1 6
3
2 7 10 1 1 5

输出 #1

16
0
12
11
10
23
15
25
7

注意

在第一个示例中,Vasya 可以创建数组 $$$(1, 5, 7, 2)$$$。那么总差值为 $$$D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16$$$。

在第二个示例中,Vasya 可用的所有整数都等于 1,因此他只能创建数组 $$$(1, 1, 1)$$$,其差值 $$$D = 0$$$。

在第三个示例中,Vasya 可以创建数组 $$$(5, 4, 3, 2, 1)$$$。那么总差将是 $$$D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12$$$。