{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBob is really interested in bipartite graph, and he needs help for this problem:\u003c/p\u003e\n\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/8f510ff9982348240b85e2d1df8c5426?v\u003d1666305101\" alt\u003d\"\"\u003e\u003c/p\u003e\n\u003cp\u003eBob has a bipartite graph which meets all the conditions below:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eThe left part has $n$ ($1\\leq n\\leq 18$) vertices, named $L_1,L_2,\\cdots,L_n$. And the right part also has $n$ vertices, named $R_1,R_2,\\cdots,R_n$.\u003c/li\u003e\n \u003cli\u003e$L_i$ \u003cstrong\u003enever\u003c/strong\u003e connects with $R_j$ when $i\u0026gt;j$ for all pairs of $(i,j)$ that $1\\leq i,j\\leq n$.\u003c/li\u003e\n \u003cli\u003eFor each vertex on the left part $L_i$ ($1\\leq i\\leq n$), its degree $D_i$ is at most $3$ and at least $1$ ($1\\leq D_i\\leq 3)$.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eBob wants to select some edges from the graph such that the selected edges and their endpoints form a new graph. However, he should obey these rules:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eSome pairs of vertices can\u0027t appear in the new graph together. You are given an $n\\times n$ matrix $A$, $A_{i,j}$ is $1$ if and only if $L_i$ and $L_j$ can\u0027t appear in the new graph together.\u003c/li\u003e\n \u003cli\u003eBob must ensure that the selected edges cover all the right vertices. In other words, every right vertex should appear in the new graph.\u003c/li\u003e\n \u003cli\u003eEvery left vertex $L_i$ ($1\\leq i\\leq n$) has a magic number $M_i$ ($1\\leq M_i\\leq 100$). If $L_i$ appears in the new graph, its cost is ${M_i}^{d_i}$, where $d_i$ is the degree of $L_i$ in the new graph, otherwise its cost is zero.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eNow Bob wants to select edges satisfying the rules above with minimum total cost. Please write a program to help him find the minimum total cost, or determine it is impossible to get such a valid new graph.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThere are several test cases in the input file. The first line contains one integer $T$ ($1\\leq T\\leq 10$) --- number of the test cases. For each case:\u003c/p\u003e\n\u003cp\u003eThe first line contains one integer $n$ ($1\\leq n\\leq 18$) --- number of the left vertices.\u003c/p\u003e\n\u003cp\u003eThe following $n$ lines are about the graph edges information with an $n\\times n$ matrix $G$. The $i$-th line contains a 01-string $G_i$ and the $j$-th character $G_{i,j}$ is $1$ if and only if $L_i$ and $R_j$ are connected, otherwise $G_{i,j}$ is $0$. We guarantee that the degree of each left vertex $L_i$ is between $1$ and $3$. We also guarantee that $G_{i,j}$ is always $0$ when $i\u0026gt;j$.\u003c/p\u003e\n\u003cp\u003eThe following line is empty.\u003c/p\u003e\n\u003cp\u003eThe following $n$ lines are about the constraints on left vertices with an $n\\times n$ matrix $A$. The $i$-th line contains a 01-string $A_i$ and the $j$-th character $A_{i,j}$ is $1$ if and only if $L_i$ and $L_j$ can\u0027t be both in $S$, which is the set of endpoints of the selected edges. We guarantee that $A_{i,i}$ ($1\\leq i\\leq n$) is $0$ and $A_{i,j}\u003dA_{j,i}$ ($1\\leq i,j\\leq n$).\u003c/p\u003e\n\u003cp\u003eThe following line is about magic numbers containing $n$ integers. The $i$-th integer $M_i$ ($1\\leq M_i\\leq 100$) is the magic number of $L_i$.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor evey case print a single line containing an integer, the minimum total cost. If it is impossible to get such a valid new graph, just output \u003ccode\u003e-1\u003c/code\u003e instead.\u003c/p\u003e"}},{"title":"Sample 1","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\u003e2\n4\n1100\n0110\n0001\n0001\n\n0001\n0001\n0000\n1100\n3 4 4 5\n4\n1100\n0110\n0001\n0001\n\n0011\n0001\n1000\n1100\n3 4 4 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003eIn the first case:\u003c/p\u003e\u003cp\u003e\u003cimg src\u003d\"https://res.jisuanke.com/img/upload/20191114/f7f7ad711042cdac7975f0fd708c2659eb124377.png\" alt\u003d\"\"\u003e\u003c/p\u003e\u003cp\u003eWe can choose edges $(L_1,R_1),(L_1,R_2),(L_2,R_3),(L_3,R_4)$ such that $S\u003d\\{L_1,L_2,L_3\\}$, satisfies the $A$ matrix\u0027s constraints. And the degrees are $d_1\u003d2,d_2\u003d1,d_3\u003d1$, so the total cost $\u003d3^2 + 4^1 + 4^1 + 0 \u003d 17$.\u003c/p\u003e\u003cp\u003eIn the second case, $R_3$ and $R_4$ can\u0027t be both covered at the same time, so there is no solution.\u003c/p\u003e"}}]}