{"problem":{"name":"Domination","description":{"content":"There are $N$ red stones and $M$ blue stones on a two-dimensional plane. The $i$\\-th red stone is at coordinates $(RX_i,RY_i)$, and the $j$\\-th blue stone is at $(BX_j,BY_j)$. There may be multiple st","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc122_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ red stones and $M$ blue stones on a two-dimensional plane. The $i$\\-th red stone is at coordinates $(RX_i,RY_i)$, and the $j$\\-th blue stone is at $(BX_j,BY_j)$. There may be multiple stones at the same coordinates.\nYou can choose a blue stone and move it to anywhere you like, any number of times. The cost of moving a blue stone from $(x, y)$ to $(x',y')$ is $|x-x'|+|y-y'|$.\nYou want to meet the following condition:\n\n*   For every $1 \\leq i \\leq N$, there are $K$ or more blue stones to the upper right of the $i$\\-th red stone. More formally, there are $K$ or more indices $1 \\leq j \\leq M$ such that $RX_i \\leq BX'_j$ and $RY_i \\leq BY'_j$, where $(BX'_j,BY'_j)$ are the coordinates of the $j$\\-th blue stone after your operations.\n\nFind the minimum total cost needed to achieve your objective.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq K \\leq \\min(M,10)$\n*   $0 \\leq RX_i,RY_i,BX_j,BY_j \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$RX_1$ $RY_1$\n$RX_2$ $RY_2$\n$\\vdots$\n$RX_N$ $RY_N$\n$BX_1$ $BY_1$\n$BX_2$ $BY_2$\n$\\vdots$\n$BX_M$ $BY_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc122_f","tags":[],"sample_group":[["3 2 1\n0 0\n2 0\n0 2\n1 0\n0 1","2\n\nThe optimal moves are as follows.\n\n*   Move the first blue stone to $(2,0)$, for the cost of $|1-2|+|0-0|=1$.\n*   Move the second blue stone to $(0,2)$, for the cost of $|0-0|+|1-2|=1$."],["3 2 2\n0 0\n2 0\n0 2\n1 0\n0 1","6\n\nThe optimal moves are as follows.\n\n*   Move the first blue stone to $(2,2)$, for the cost of $|1-2|+|0-2|=3$.\n*   Move the second blue stone to $(2,2)$, for the cost of $|0-2|+|1-2|=3$."],["10 10 3\n985971569 9592031\n934345597 151698665\n212173157 492617927\n623299445 288193327\n381549360 462770084\n681791249 242910920\n569404932 353061961\n357882677 463919940\n110389433 533715995\n9639432 700209424\n771167518 75925290\n439954587 566974581\n738467799 122646638\n267815107 900808287\n886340750 70087431\n434010239 822484872\n388269208 879859813\n393002209 874330449\n154134229 924857472\n667626345 460737380","1165266772"]],"created_at":"2026-03-03 11:01:14"}}