分数: 1200 点
问题陈述
有 N 红色宝石和 M 二维平面上的蓝色宝石。 的 i-第一个红石位于坐标处 (RX_i,RY_i),以及 j第一个蓝色石头位于 (BX_j,BY_j)。 同一坐标处可能有多个石头。
你可以选择一块蓝色石头并将其移动到你喜欢的任何地方,任意次数。 移动一颗蓝色宝石的费用 (x, y) to (x',y') is |x-x'|+|y-y'|.
您希望满足以下条件:
- 对于每个 1 \leq i \leq N,有 K 或更多蓝色宝石到右上角 i-第一个红色石头。 更正式地说,有 K 或更多索引 1 \leq j \leq M 这样 RX_i \leq BX'_j 和 RY_i \leq BY'_j,其中 (BX'_j,BY'_j) 是坐标 j- 操作后的第一个蓝色石头。
找出实现目标所需的最低总成本。
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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
3 2 1 0 0 2 0 0 2 1 0 0 1
示例输出 1
2
最佳移动如下。
- 将第一个蓝色石头移至 (2,0),费用为 |1-2|+|0-0|=1.
- 将第二块蓝色石头移至 (0,2),费用为 |0-0|+|1-2|=1.
示例输入 2
3 2 2 0 0 2 0 0 2 1 0 0 1
示例输出 2
6
最佳移动如下。
- 将第一个蓝色石头移至 (2,2),费用为 |1-2|+|0-2|=3.
- 将第二块蓝色石头移至 (2,2),费用为 |0-2|+|1-2|=3.
示例输入 3
10 10 3 985971569 9592031 934345597 151698665 212173157 492617927 623299445 288193327 381549360 462770084 681791249 242910920 569404932 353061961 357882677 463919940 110389433 533715995 9639432 700209424 771167518 75925290 439954587 566974581 738467799 122646638 267815107 900808287 886340750 70087431 434010239 822484872 388269208 879859813 393002209 874330449 154134229 924857472 667626345 460737380
示例输出 3
1165266772