In a kingdom far, far away there are N cities numbered 1 through N, some pairs of cities being connected by roads. When two cities are directly connected by a road, we will say these cities are neighbors. As a result of the careful planning of its monarchs, the kingdom's road system has very special characteristics. We know there are no two cities connected by more than one road, and that all roads connect different cities. Another very peculiar property of the roads is that there is exactly one path between any two cities, consisting of a sequence of roads connecting neighboring cities from the initial to the final one.

In this kingdom far, far away, the king wants to impose curling as the national sport. He therefore wants each city to have a favorite curling team, so that the feeling of belonging of its citizens is enhanced by all of them supporting the same team. There are some cities which already have a favorite team, and because curling is a deep passion these choices cannot be changed. However, other cities don't yet have a favorite curling team, so one will have to be assigned to them in order for it to become the city's favorite.

The president of the Institute for the Competitive Practice of Curling (ICPC) has requested your help, because the king has entrusted it with assigning the favorite teams for the cities that don't yet have one. The problem is that there are too many cities in the kingdom, so the ICPC doesn't really know how to complete this task. We know there are E curling teams which have been numbered 1 through E, and there is no budget to create more. The ICPC has provided you with a riot index between teams for every pair of teams, i.e. an integer D_ij representing the degree of hostility between followers of teams i and j, for i, j = 1, 2, ..., E. Note that there even exists a riot index for a given team with itself, as it is possible that inhabitants of two neighboring cities with the same favorite team start to fight in order to see which one has the best following.

The ICPC has asked you to assign a favorite team to every city in the kingdom not having one yet, in such a way that the riots between neighboring cities are minimized. In order to do this, you should minimize the national riot index, which is calculated by summing all the riot indices for teams assigned to neighboring cities. Can you help the ICPC determine the minimum possible value of the national riot index?

Input

There are multiple test cases in the input file. For each test case, the first line contains two integers N and E, representing respectively the number of cities and the number of curling teams in the kingdom (2 ≤ N ≤ 5 * 10⁴ and 1 ≤ E ≤ 50). The following E lines describe the riot indices between the curling teams. Each of these lines contains E integers, the j-th integer of the i-th of these lines being D_ij, the riot index between teams i and j (0 ≤ D_ij ≤ 1000 with D_ij = D_ji for i, j = 1, 2, ..., E).

The following E lines describe the favorite teams of the cities which have already chosen one. The i-th of these lines starts with a non-negative integer K_i followed by a list of K_i cities whose favorite team is number i (0 ≤ K_i ≤ N for i = 1, 2, ..., E). No city has more than one favorite team, and there are no repeated cities in the lists.

The last N-1 lines describe the roads between the kingdom's cities. Each of them contains two integers A and B, indicating that there is a road between city A and city B (1 ≤ A, B ≤ N with A ≠ B). The roads are bidirectional and there are no repeated roads in the input. It is guaranteed that there is a unique path between every pair of cities, possibly going through other intermediate cities.

Output

For each test case, print one line containing an integer representing the minimum value of the national riot index that can be achieved by optimally assigning the favorite teams.

Example

Input:
3 2
2 1
1 2
0
0
1 2
1 3
6 3
3 2 1
2 3 4
1 4 3
2 1 3
0
0
1 2
1 3
1 4
3 5
3 6

Output:
2
7