#5771. 「CEOI2026」塔

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 CEOI 2026 Day2 T1「Towers」

在一条直线上，有 $n$ 台计算机和 $m$ 座塔，它们的所在位置各不相同。你需要用电线将计算机两两配对，使得每条电线从某台计算机出发，途径若干座塔，最终连接到另一台计算机。

电线可以按任意顺序访问任何塔（不仅限于两台计算机之间的塔）。它可以在路过某些塔时不访问它们，也可以完全不访问任何塔而直接连接两台计算机，但不能将一台计算机连接到其自身。计算机的数量 $n$ 是偶数。

设 $a$ 和 $b$ 为两台计算机的位置，并设 $x_1, \dots, x_k$ 为电线途径访问的塔的位置。该电线的长度为 $|a - x_1| + |x_1 - x_2| + \dots + |x_{k-1} - x_k| + |x_k - b|$。对于一条电线，我们将其得分定义为 $f \cdot u - l$，其中 $l$ 是该电线的长度，$f$ 为给定的常数，而 $u$ 是电线在 $x_1, \dots, x_k$ 中访问过的不同塔的数量。

多条电线可以访问同一座塔，并且该塔会对所有访问它的电线的得分产生贡献。

你需要计算将所有计算机两两配对后（即每台计算机必须恰好属于一个对，或者等价地，必须恰好连接一条电线），所有电线得分之和的最大可能值。

输入格式

第一行包含测试用例的数量 $T$。测试用例依次给出。

每个测试用例包含三行： 第一行包含三个整数 $n, m$ 和 $f$，分别表示计算机的数量、塔的数量以及常数 $f$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示各计算机的位置。 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$，表示各塔的位置。

输出格式

输出 $T$ 个整数，每个整数各占一行，分别表示每个测试用例中电线得分之和的最大可能值。

样例

输入

4
2 1 100
1 10
11
4 1 10
2 4 6 8
20
4 1 10
2 4 6 8
5
6 3 10
2 13 4 8 6 10
5 1 9

输出

89
-4
12
51

在第一个样例中：

• 对于第 $1$ 个测试用例，将位置在 $1$ 和 $10$ 的两台计算机配对，电线途径位于 $11$ 的塔。电线访问了 $1$ 座不同的塔，长度为 $|1 - 11| + |11 - 10| = 10 + 1 = 11$。得分等于 $100 \cdot 1 - 11 = 89$。这是最大可能的得分。
• 对于第 $2$ 个测试用例，最佳方案是不访问任何塔（因为塔太远，得不偿失），将 $(2, 4)$ 和 $(6, 8)$ 分别配对，得分和为 $-(2 + 2) = -4$。
• 对于第 $3$ 个测试用例，将位于 $4$ 和 $6$ 的计算机通过位于 $5$ 的塔连接，得分等于 $10 \cdot 1 - (|4 - 5| + |5 - 6|) = 10 - 2 = 8$；将位于 $2$ 和 $8$ 的计算机直接连接，得分等于 $-|2 - 8| = -6$。总得分为 $8 + (-6) = 2$。若两对计算机均通过位于 $5$ 的塔连接，则得分分别为 $10 - 2 = 8$ 和 $10 - 6 = 4$，总得分为 $8 + 4 = 12$。
• 对于第 $4$ 个测试用例，最大可能得分之和为 $51$。

数据范围与提示

设 $N$ 和 $M$ 分别为所有测试用例中 $n$ 和 $m$ 的总和。对于所有输入数据，满足：

• $1 \leq T \leq 10^4$
• $1 \leq N, M \leq 2 \cdot 10^5$
• $0 \leq f \leq 10^9$
• $n$ 为偶数
• $1 \leq a_i, b_i \leq 10^9$
• 在单个测试用例中，所有计算机和塔的位置均互不相同。

详细子任务附加限制及分值如下表所示。