Efficient Tree

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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.

Input

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$.

Output

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$.

Sample Input

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

Sample Output

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

Hint

wange2014

Source

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

提交代码