P12618 [RMI 2023] Statues

翻译来自 [LibreOJ](https://loj.ac/p/4803)。

`` 想要拿到一张新的 `C chart`，而这张图表只能在 `` 岛的 `` 神殿里找到。要进入神殿，他得先解开一个谜题。 `` 需要进入一个 $T$ 维空间，这里每个点的坐标都由一个长度为 $T$ 的数组表示，比如 $[x_1, x_2, x_3, \dots, x_T]$。在这个空间里，有 $N$ 个固定不动的雕像（编号从 $1$ 到 $N$）和 $Q$ 个可以移动的雕像（编号从 $1$ 到 $Q$）。`` 最多可以移动 **$K$ 次**，每次他可以选择一个**可移动的雕像**，然后沿着某个轴的方向移动它一个单位。也就是说，某个雕像的坐标会变成 $[x_1, x_2, \dots, x_i−1, \dots, x_T]$ 或 $[x_1, x_2, \dots, x_i+1, \dots, x_T]$。 为了打开 `` 神殿的大门，他需要调整这些**可移动雕像**的位置，让所有**可移动雕像**与所有**固定雕像**之间的曼哈顿距离之和尽可能小。 两个 $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$，分别表示固定雕像的数量、空间维数以及 `` 最多可以移动的次数。 接下来的 $N$ 行，每行有 $T$ 个用空格分隔的整数。第 $i$ 行表示第 $i$ 个**固定雕像**的坐标。 再下一行是一个单独的整数 $Q$，表示**可移动雕像**的数量。 接下来的 $Q$ 行，每行有 $T$ 个用空格分隔的整数，以类似的方式表示每个**可移动雕像**的坐标。

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

### 数据范围与提示 对于所有输入数据，满足： * $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$ | 无附加限制 |