{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 2 1\n0 0\n2 0\n0 2\n1 0\n0 1"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"3 2 2\n0 0\n2 0\n0 2\n1 0\n0 1"},{"iden":"sample output 2","content":"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$."},{"iden":"sample input 3","content":"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"},{"iden":"sample output 3","content":"1165266772"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}