Sword

Satoshi, who has strong obsessions with Chinese domestic RPG, will never miss the marvelous game, Gu Jian Qi Tan II, a.k.a., the Legend of Ancient Sword II, because of its gorgeous graphics, picturesque characters and lively design.

Recently, Satoshi has some troubles in the new battle mode of the game, and seeks you for help to solve the problems.

Specifically, in the new instant-action mode, Satoshi can control N roles, and his goal is to kill all M tiny monsters to declare victory. The tiny monsters are too fragile to survive from any skills of any roles. In every second, Satoshi can choose to operate one single role once, or do nothing. However, to make his series of operations magnificent, he would not use same role in any two consecutive seconds, i.e., the role used in i-th second cannot be used in the (i+1)-th second anymore.

For each role, we know the number of skills he/she owns, as well as the LPT (loop time) of each skill, which indicates that the skill could be performed in every LPT seconds starting from the beginning (e.g., if the LPT of a skill is 3, Satoshi could cast the skill at 3s, 6s, 9s, ..., so on and so forth). Moreover, the information of whether a skill can reach (touch) a certain monster is also provided (i.e., whether a monster is within the attacking range of a specific skill). Your task is to help Satoshi use the minimum amount time to win the game; ties are broken by preferring fewer number of operations, which is counted by the number of seconds in which Satoshi chooses to operate a role instead of doing nothing.

Note that Satoshi could choose a certain role, and of course no roles, in a specific second. And when he operates a role in a specific second, he can cast all the available skills (subject to the the LPT constraints) if he wants. Time begins with the 1st second.

The integer R in the first line of input indicates the total number of test cases. For each test case, there are two integers N (1 <= N <= 10) and M (1 <= M <= 200) as stated above, in the first line. Then N blocks of input follow. For the i-th block, the first line contains an integer S_i (1 <= S_i <= 300) denoting the number of skills that the i-th role owns. Each of the the next S_i lines in the i-th block has M+1 integers, i.e., the LPT (1 <= LPT <= 6) of the i-th role, and M Boolean values (0/1) where the j-th Boolean value indicates if the j-th monster is within the attacking range of the i-th role.

For each test case, print the minimum number of seconds T by which Satoshi could win the game, as well as the corresponding minimum number of operations that Satoshi has to perform (in T seconds), in a single line; if it is impossible for Satoshi to win, output nothing but a zero in a single line.

4

1 1
1
1 1

1 1
1
3 1

2 2
2
1 1 0
2 1 0
1
1 1 0

1 2
3
2 1 0
5 0 1
6 1 1

1 1
3 1
0
5 2

2013 ACM/ICPC Asia Regional Changchun Online