AT_arc122_f [ARC122F] Domination

[problemUrl]: https://atcoder.jp/contests/arc122/tasks/arc122_f 二次元平面上に $ 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 $ - 入力される値はすべて整数である ### Sample Explanation 1 以下の操作を行えばよいです． - $ 1 $ 番目の青い石を座標 $ (2,0) $ に動かす．コストが $ |1-2|+|0-0|=1 $ かかる． - $ 2 $ 番目の青い石を座標 $ (0,2) $ に動かす．コストが $ |0-0|+|1-2|=1 $ かかる． ### Sample Explanation 2 以下の操作を行えばよいです． - $ 1 $ 番目の青い石を座標 $ (2,2) $ に動かす．コストが $ |1-2|+|0-2|=3 $ かかる． - $ 2 $ 番目の青い石を座標 $ (2,2) $ に動かす．コストが $ |0-2|+|1-2|=3 $ かかる．