题目描述

一条直线上有 $n$ 台计算机和 $m$ 座塔，它们的位置两两不同。你需要使用线缆将计算机两两配对，使每根线缆从某台计算机出发，经过若干座塔，最终到达另一台计算机。线缆可以按任意顺序经过任意一些塔，不必只经过两台计算机之间的塔。线缆经过某座塔旁边时可以跳过它而不访问。线缆也可以不访问任何塔，直接连接两台计算机，但不能将一台计算机连接到自身。计算机数量为偶数。

设 $a$ 和 $b$ 是两台计算机的位置，$x_1,\ldots,x_k$ 是线缆所访问的塔的位置。该线缆的长度为 $|a-x_1|+|x_1-x_2|+\cdots+|x_{k-1}-x_k|+|x_k-b|$。对于一根线缆，将其得分定义为 $f\cdot u-l$，其中 $l$ 是线缆长度，$f$ 是某个固定常数，$u$ 是 $x_1,\ldots,x_k$ 中线缆访问过的不同塔的数量。多根线缆可以访问同一座塔，而且该塔会分别计入每根线缆的得分。

你需要将所有计算机两两配对，并求线缆得分总和的最大可能值。也就是说，每台计算机都必须恰好属于一个配对；等价地，每台计算机都必须恰好连接一根线缆。

输入格式

第一行包含测试用例数量 $T$，随后依次给出各个测试用例。每个测试用例包含三行。第一行包含三个整数 $n$、$m$ 和 $f$，分别表示计算机数量、塔的数量以及常数 $f$。第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各台计算机的位置。第三行包含 $m$ 个整数 $b_1,b_2,\ldots,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

提示

限制条件

分别以 $N$ 和 $M$ 表示所有测试用例中 $n$ 与 $m$ 的总和。

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

子任务

• 子任务 $1$（$5$ 分）：$N\le 5000$，$m=1$
• 子任务 $2$（$10$ 分）：$T\le 20$，$n\le 10$，$m\le 100$
• 子任务 $3$（$27$ 分）：$N,M\le 5000$
• 子任务 $4$（$21$ 分）：$N\le 5000$
• 子任务 $5$（$37$ 分）：无额外限制。

翻译由 ChatGPT-5.6 完成