配点 : $1200$ 点

問題文

二次元平面上に $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$ 番目の青い石の操作後の座標である．

目標達成のためにかかるコストの合計の最小値を求めてください．

制約

• $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$

出力

答えを出力せよ．

3 2 1
0 0
2 0
0 2
1 0
0 1

2

以下の操作を行えばよいです．

• $1$ 番目の青い石を座標 $(2,0)$ に動かす．コストが $|1-2|+|0-0|=1$ かかる．
• $2$ 番目の青い石を座標 $(0,2)$ に動かす．コストが $|0-0|+|1-2|=1$ かかる．

3 2 2
0 0
2 0
0 2
1 0
0 1

6

以下の操作を行えばよいです．

• $1$ 番目の青い石を座標 $(2,2)$ に動かす．コストが $|1-2|+|0-2|=3$ かかる．
• $2$ 番目の青い石を座標 $(2,2)$ に動かす．コストが $|0-2|+|1-2|=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

1165266772