{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n A graph $G$ with $n\\times m$ nodes forms a $n\\times m$ grid with $n\\times m$ vertices.\u003cbr\u003e\n $(n-1)\\times m$ weighted edges connect the vertices of adjacent rows, and $n\\times(m-1)$ weighted edges connect the vertices of adjacent columns.\u003cbr\u003e\u003cbr\u003e\n A spanning tree of graph $G$ is a subgraph that is a tree and connects all the vertices together.\u003cbr\u003e\n A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.\u003cbr\u003e\n Graph $G$ has many different minimum spanning trees.\u003cbr\u003e\n For each MST $T$, the $LRdeg(u)$ of node $u$ is defined as the number of nodes, in the previous column or the previous row connecting with $u$, plus one.\u003cbr\u003e\n And we define $\\tau(T)\u003d\\prod_u LRdeg(u)$ as the product of $LRdeg(u)$ for all nodes.\u003cbr\u003e\u003cbr\u003e\n Your mission is to find the weight of the minimum spanning tree of graph $G$, and count $\\tau(T)$ of all minimum spanning trees. Two MST(s) are considered different if they contain different subsets of edges.\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains several test cases. The first line of the input is a single integer $t~(1\\le t\\le 32)$ which is the number of test cases. Then $t$ test cases follow.\u003cbr\u003e\u003cbr\u003e\nFor each test case, the first line contains the two integers $n~(1\\le n\\le 800)$ and $m~(1\\le m\\le 7)$.\u003cbr\u003e\nEach line of the next $n$ lines contains $m-1$ integers, which describe the weights of edges connecting the vertices of adjacent columns.\u003cbr\u003e\nAnd each line of the next $n-1$ lines contains $m$ integers, which describe the weights of edges connecting the vertices of adjacent rows. The weights of edges are no more than $10$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, you should output two integers in one line. The first one is the weight of the minimum spanning tree.\u003cbr\u003e\nThe second one is the sum of $\\tau(T)$ for all different minimum spanning trees, modulo $10^9+7$."}},{"title":"Sample","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\u003e\u003cpre\u003e2\r\n\r\n2 5\r\n9 8 5 6\r\n4 6 2 3\r\n1 7 8 3 8\r\n\r\n5 5\r\n8 10 5 4\r\n1 7 7 7\r\n5 4 5 5\r\n3 2 2 2\r\n8 7 8 3\r\n8 5 7 8 6\r\n10 3 2 4 3\r\n8 7 2 8 9\r\n9 4 8 3 9\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003eCase #1: 37 288\r\nCase #2: 96 4478976\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}