问题描述

在一个二维平面上有$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$，存在$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