Efficient Tree

A graph $G$ with $n\times m$ nodes forms a $n\times m$ grid with $n\times m$ vertices.
$(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.

A spanning tree of graph $G$ is a subgraph that is a tree and connects all the vertices together.
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.
Graph $G$ has many different minimum spanning trees.
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.
And we define $\tau(T)=\prod_u LRdeg(u)$ as the product of $LRdeg(u)$ for all nodes.

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.

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.

For each test case, the first line contains the two integers $n~(1\le n\le 800)$ and $m~(1\le m\le 7)$.
Each line of the next $n$ lines contains $m-1$ integers, which describe the weights of edges connecting the vertices of adjacent columns.
And 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$.

For each test case, you should output two integers in one line. The first one is the weight of the minimum spanning tree.
The second one is the sum of $\tau(T)$ for all different minimum spanning trees, modulo $10^9+7$.

2

2 5
9 8 5 6
4 6 2 3
1 7 8 3 8

5 5
8 10 5 4
1 7 7 7
5 4 5 5
3 2 2 2
8 7 8 3
8 5 7 8 6
10 3 2 4 3
8 7 2 8 9
9 4 8 3 9

Case #1: 37 288
Case #2: 96 4478976

2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）