{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e众所周知,六花不擅长数学。友太为此担忧,于是给了六花一些数学练习题。其中有一道题目:\u003cbr\u003e\u003cbr\u003e友太手上有一个图,有$n$个节点$(i,j)(1 \\leq i \\leq n,1 \\leq j \\leq m)$。如果且仅如果$|a-c|+|b-d|\u003d1$,则$(a,b)$和$(c,d)$之间有一条边。每条边都有自己的权重。\u003cbr\u003e\u003cbr\u003e现在友太想要计算出$G$的最小权重$K$-匹配。\u003cbr\u003e\u003cbr\u003e这对六花来说太难了。你能帮帮她吗?\u0026nbsp;\u0026nbsp;\u003cbr\u003e\u003cbr\u003e一组边$S$是$G\u003d\\langle V,E \\rangle$的匹配,如果且仅如果$V$中的每个节点连接至多一条$S$中的边。一个匹配$S$是$K$-匹配,如果且仅如果$|S|\u003dK$。匹配$S$的权重是$S$中边的权重之和。最后,$G$的最小权重$K$-匹配被定义为$G$中最小权重的$K$-匹配。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个数字$t(1 \\leq t \\leq 1000)$,表示测试用例的数量。每个测试用例不超过$3$个,每个有$n \u0026gt; 100$。\u003cbr\u003e\u003cbr\u003e对于每个测试用例,第一行包含三个数字$n,m,K(1 \\leq n \\leq 4 \\times 10^4,1 \\leq m \\leq 4),1 \\leq K \\leq \\lfloor \\frac{nm}{2} \\rfloor$。\u003cbr\u003e\u003cbr\u003e接下来有$n-1$行,每行包含$m$个数字$A_{i,j}(1 \\leq A_{i,j} \u003cbr\u003e\\leq 10^9)$ -- $(i,j)$和$(i+1,j)$之间边的权重。\u003cbr\u003e\u003cbr\u003e如果$m\u0026gt;1$,则接下来$n$行,每行包含$m-1$个数字$B_{i,j}(1 \\leq B_{i,j} \\leq 10^9)$ -- $(i,j)$和$(i,j+1)$之间边的权重。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行一个数字 -- 答案。\u003cbr\u003e\u003cbr\u003e保证至少存在一个$K$-匹配。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3 3 1\r\n3 4 5\r\n8 9 10\r\n1 2\r\n6 7\r\n11 12\r\n3 3 2\r\n3 4 5\r\n8 9 10\r\n1 2\r\n6 7\r\n11 12\r\n3 3 3\r\n3 4 5\r\n8 9 10\r\n1 2\r\n6 7\r\n11 12\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n5\r\n12\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}