AT_arc122_f [ARC122F] Domination

在二维平面上有 $N$ 个红色石子和 $M$ 个蓝色石子。第 $i$ 个红色石子位于坐标 $(RX_i, RY_i)$，第 $j$ 个蓝色石子位于坐标 $(BX_j, BY_j)$。同一坐标上可以有多个石子。 你可以无限次地选择一个蓝色石子并将其移动到任意坐标。将坐标为 $(x, y)$ 的蓝色石子移动到 $(x', y')$ 时，所需的代价为 $|x - x'| + |y - y'|$。 你的目标是使得以下条件成立： - 对于所有 $1 \leq i \leq N$，第 $i$ 个红色石子的右上区域内至少存在 $K$ 个蓝色石子。更严格地说，满足 $RX_i \leq BX'_j$ 且 $RY_i \leq BY'_j$ 的 $1 \leq j \leq M$ 的个数不少于 $K$。其中 $(BX'_j, BY'_j)$ 表示第 $j$ 个蓝色石子操作后的坐标。 请你求出达成目标所需的总代价的最小值。

输入以如下格式从标准输入给出。 > $N$ $M$ $K$ $RX_1$ $RY_1$ $RX_2$ $RY_2$ $\vdots$ $RX_N$ $RY_N$ $BX_1$ $BY_1$ $BX_2$ $BY_2$ $\vdots$ $BX_M$ $BY_M$

请输出答案。

### 限制条件 - $1 \leq N \leq 10^5$ - $1 \leq M \leq 10^5$ - $1 \leq K \leq \min(M, 10)$ - $0 \leq RX_i, RY_i, BX_j, BY_j \leq 10^9$ - 输入的所有值均为整数 ### 样例解释 1 可以进行如下操作： - 将第 $1$ 个蓝色石子移动到坐标 $(2, 0)$，代价为 $|1-2| + |0-0| = 1$。 - 将第 $2$ 个蓝色石子移动到坐标 $(0, 2)$，代价为 $|0-0| + |1-2| = 1$。 ### 样例解释 2 可以进行如下操作： - 将第 $1$ 个蓝色石子移动到坐标 $(2, 2)$，代价为 $|1-2| + |0-2| = 3$。 - 将第 $2$ 个蓝色石子移动到坐标 $(2, 2)$，代价为 $|0-2| + |1-2| = 3$。 由 ChatGPT 4.1 翻译