{"trustable":false,"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":"PLAIN","content":"给定n * n矩阵C ij(1 \u003c\u003d i,j \u003c\u003d n),我们要找到0或1的n * n矩阵X ij(1 \u003c\u003d i,j \u003c\u003d n)。\n此外,X ij满足以下条件:\n1.X 12 + X 13 + ... X 1n \u003d 1\n2.X 1n + X 2n + ... X n-1n \u003d 1\n3.对于每个i(1 \u003ci \u003cn),满足ΣXki(1 \u003c\u003d k \u003c\u003d n)\u003dΣXij(1 \u003c\u003d j \u003c\u003d n)。\n例如,如果n \u003d 4,我们可以得到以下等式:\nX 12 + X 13 + X 14 \u003d 1\nX 14 + X 24 + X 34 \u003d 1\nX 12 + X 22 + X 32 + X 42 \u003d X 21 + X 22 + X 23 + X 24\nX 13 + X 23 + X 33 + X 43 \u003d X 31 + X 32 + X 33 + X 34\n现在,我们想知道你可以得到的最小ΣCij * X ij(1 \u003c\u003d i,j \u003c\u003d n)。"}},{"title":"Input","value":{"format":"PLAIN","content":"The input consists of multiple test cases (less than 35 case). \nFor each test case ,the first line contains one integer n (1\u003cn\u003c\u003d300). \nThe next n lines, for each lines, each of which contains n integers, illustrating the matrix C, The j-th integer on i-th line is Cij(0\u003c\u003dCij\u003c\u003d100000)."}},{"title":"Output","value":{"format":"PLAIN","content":"For each case, output the minimum of ∑C ij*X ij you can get. "}},{"title":"Sample Input","value":{"format":"PLAIN","content":"4\n1 2 4 10\n2 0 1 1\n2 2 0 5\n6 3 1 2"}},{"title":"Sample Output","value":{"format":"PLAIN","content":"3"}}]}