Gu Jian Qi Tan(古剑奇潭) is a popular Chinese RPG. As an RPG fan, Gaewah surely won't miss it. So he bought it and started his research. In the world of Gu Jian Qi Tan, every soul owns a unique memory mint-mark which inherits from ancient times. The mint-mark includes the secret of lives and mana power, and it is a graph in essence, we call it XingYun(星蕴) graph.

Every soul has a unique XingYun graph and every graph has many XingYun pools. Each pool can be linked with one or more other pools. In this world, there is a special substance called XingPo(星魄). When you get one, you must set a property to it. The property could be Gold, Wood, Water, Fire or Earth. Putting it into an XingYun pool, the power of the soul can be improved. XingPo can give you 3 kinds of power, namely nature ability point, magic skills and Kung Fu. Detailed rules are listed below.

Nature ability: When you put a XingPo with some property into a XingYun pool, the soul can gain some nature ability points of corresponding property. Putting XingPo with property i into XingYun pool j will gain you nature ability point p[i][j]. Each pool can contain one XingPo only.

Magic skill: We have 5 kinds of magic skills (gold, wood, water, fire, earth) in total, and each skill has 6 levels. With some adjacent pools containing XingPo with the same property, you will learn a magic skill of the property. When 3, 4, 6, 8, 10 or 12 pool, you will learned the level 1, 2, 3, 4, 5 or 6 magic skill correspondingly. But be careful that each level of the magic skills with the same property can only be learned once! As in the figure below, you will learn magic that dark color represent level 1 and level 2, and magic light color represent level 1.(Here dark color and light color just represent two different magic among gold, wood, water, fire, earth)

Kung Ku: Every XingYun graph has K connected sub-graph. If all the pools in one sub-graph are filled with XingPo, you will learn the Kung Ku of this sub-graph.

To simplify this problem, nature ability, each level of magic skills of different properties and each Kung Ku have be assigned a value. Given a XingYun Graph with K part of sub-graph and the number of XingPo you have. Please put all XingPo into pools, and tell me the maximum total value.

First line is an integer T, which means T test cases in total.

For each case:

The first line has two integers N and K, indicating that you have N XingPo and the XingYun graph has K connected sub-graph (N<=24, K<=2).

Next K blocks each describes a sub-graph.

The first line in each block has two integers Mi (1<=Mi<=12) and Vi, indicating the i-th connected sub-graph has Mi XingYun pools and the value of the Kung Fu of this sub-graph is Vi.

Next 5 lines in each block is the p matrix and each line has Mi integers. Putting XingPo with property i into XingYun pool j will gain you nature ability point p[i][j].

Given that each sub-graph only contains Mi-1 edge between pools, you can regard the sub-graph as a tree. The next Mi-1 lines each has two numbers a and b, indicating that there is an edge between node a and node b. All edges are bidirectional and we guaranteed the all pools in a sub-graph are linked.

After K blocks, there are 5 lines. Each line has 6 numbers.

The j-th number in the i-th line is the value of the magic skill i of level j.

All the number given in the input would not exceed 1000.

Print "Case #X:" (X is the case number) in the first line of each test case.

The second line is an integer indicating the maximum total value.

1
12 2
11 1000
3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 9
5 10
10 11
12 900
3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 9
6 10
10 11
11 12
30 40 60 80 100 120
30 40 60 80 100 120
30 40 60 80 100 120
30 40 60 80 100 120
30 40 60 80 100 120

Case #1: 1366