← 返回题目列表

AtCoder · arc122_f

F. 统治

中文机器翻译题面 查看原题

分数: 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