Animal Farm

You run a farm with $N$ animals ($1 \le N \le 100$). From a store you bought $M = N$ pre-made pens to house them. The pens satisfy the following conditions:

• each pen has between $3$ and $8$ edges (walls);
• an edge that appears in two pens joins those two pens together;
• an edge that appears in only one pen connects that pen to the outside (the area outside every pen);
• initially there is exactly one animal in each pen and no animals outside the pens.

The animals love a game called "Escape from the pen." Every edge has a cost, and the animals want the minimum total cost to make all of them gather in the same area by trampling down the walls of various pens. The animals may gather inside one particular pen, or outside all of the pens. Once an edge has been trampled down, any animal may cross it afterwards at no additional cost.

Given the description of the pens and the placement of the animals, determine the smallest cost needed to move all of the animals into the same area.

The first line contains the integer $M$, the number of pens. Each of the next $M$ lines describes one pen. A description consists of three parts separated by single spaces:

• the first part is an integer $e_p$ ($3 \le e_p \le 8$), the number of edges of pen $p$;
• the second part is a sequence of $e_p$ integers giving the corners of the pen, where each integer is at most $1000$;
• the third part is a sequence of $e_p$ integers giving the cost of each edge, where each integer is at most $5000$.

The corners and edge costs are listed in cyclic order. For example, the pen description

3 1 2 3 7 4 6

means the pen has three corners (and therefore three edges), where edge $(1, 2)$ has cost $7$, edge $(2, 3)$ has cost $4$, and edge $(3, 1)$ has cost $6$.

Output on a single line the minimum cost that lets all of the animals gather inside one pen or outside all of the pens.