题目描述

题目译自 Romanian Master of Informatics 2023 Day2 T2 「Statues」

<Link /> 想要拿到一张新的 C chart，而这张图表只能在 <meta> 岛的 <element> 神殿里找到。要进入神殿，他得先解开一个谜题。

<Link /> 需要进入一个 $T$ 维空间，这里每个点的坐标都由一个长度为 $T$ 的数组表示，比如 $[x_1, x_2, x_3, \dots, x_T]$。在这个空间里，有 $N$ 个固定不动的雕像（编号从 $1$ 到 $N$）和 $Q$ 个可以移动的雕像（编号从 $1$ 到 $Q$）。<Link /> 最多可以移动 $K$ 次，每次他可以选择一个可移动的雕像，然后沿着某个轴的方向移动它一个单位。也就是说，某个雕像的坐标会变成 $[x_1, x_2, \dots, x_i−1, \dots, x_T]$ 或 $[x_1, x_2, \dots, x_i+1, \dots, x_T]$。

为了打开 <element> 神殿的大门，他需要调整这些可移动雕像的位置，让所有可移动雕像与所有固定雕像之间的曼哈顿距离之和尽可能小。

两个 $T$ 维点 $[x_1, x_2, \dots, x_T]$ 和 $[y_1, y_2, \dots, y_T]$ 之间的曼哈顿距离定义为：

$$\operatorname{dist}([x_1, x_2, \dots, x_T], [y_1, y_2, \dots, y_T]) = \displaystyle \sum_{i = 1}^{T} |x_i - y_i| $$

假设 $s$ 是所有固定雕像的坐标数组，$m$ 是经过最多 $K$ 次最优移动后所有可移动雕像的坐标数组。你需要计算：

$$\displaystyle \sum_{i = 1}^{N} \sum_{j = 1}^{Q} \operatorname{dist}(s_i, m_j) $$

输入格式

第一行包含三个整数 $N, T, K$，分别表示固定雕像的数量、空间维数以及 <Link /> 最多可以移动的次数。

接下来的 $N$ 行，每行有 $T$ 个用空格分隔的整数。第 $i$ 行表示第 $i$ 个固定雕像的坐标。

再下一行是一个单独的整数 $Q$，表示可移动雕像的数量。

接下来的 $Q$ 行，每行有 $T$ 个用空格分隔的整数，以类似的方式表示每个可移动雕像的坐标。

输出格式

输出一个整数，表示在最多 $K$ 次移动后，所有固定雕像到所有可移动雕像的曼哈顿距离之和的最小值。

3 2 7
8 1
2 0
0 3
2
10 2
2 6

29

6 4 200
12 1 19 10
45 3 42 44
42 32 40 41
39 12 32 47
35 18 40 20
38 14 25 1
3
34 10 7 9
29 32 21 50
16 36 18 38

708

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, Q \leq 100\ 000$
• $1 \leq T \leq 10$
• $1 \leq K \leq 10^{15}$
• 所有坐标都是 $0$ 到 $10^9$ 之间的整数（包含边界）。
• 答案保证能用 64 位有符号整数表示。

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

子任务	分值	附加限制
$1$	$7$	$T = Q = 1$
$2$	$10$	$N, Q, K \leq 100$
$3$	$12$	$N, Q \leq 50$
$4$	$28$	$T = 1$
$5$	$17$	$Q = 1$
$6$	$26$	无附加限制