Parks of Jakarta

There are three parks in Jakarta: Park 1, Park 2, and Park 3. The new governor of Jakarta wants to decorate these parks by stacking bricks in them. There are $N$ bricks in Jakarta, numbered from $1$ to $N$, where a smaller number means a smaller brick. A bigger brick must never sit on top of a smaller brick, so brick $i$ may be placed directly on top of brick $j$ only when $i < j$.

A brick configuration is a distribution of the $N$ bricks over the three parks. Each park holds at most one stack of bricks, and every stack must respect the rule above. For example, when $N = 3$, one valid configuration keeps brick $1$ (on top) and brick $2$ (at the bottom) in Park 1, leaves Park 2 empty, and keeps brick $3$ in Park 3.

One operation transforms a configuration as follows.

• Choose two different parks $i$ and $j$. Take the topmost brick of the stack in Park $i$ and place it on top of the stack in Park $j$. The operation is invalid when Park $i$ is empty, and it is also invalid when the resulting stack in Park $j$ breaks the stacking rule.
• Moving a brick requires a rented truck, so each move from Park $i$ to Park $j$ costs $R_{i,j}$. The cost from Park $i$ to Park $j$ may differ from the cost from Park $j$ to Park $i$.

The process starts from a given initial configuration. The governor wants to see each of $M$ chosen configurations at least once, in any order. At the end, all bricks must stand stacked in a single park. Find the minimum possible total cost.

Formally, let the desired configurations be $G_1, G_2, \dots, G_M$. Find a sequence of configurations $C_0, C_1, \dots, C_k$ ($k \ge 0$) with minimum cost such that:

• $C_0$ is the initial configuration.
• For every desired configuration $G$ there is an integer $x$ ($0 \le x \le k$) with $C_x = G$. The visiting order does not matter.
• In $C_k$ all bricks are stacked in one park.
• For every $0 \le i < k$, $C_{i+1}$ is obtained from $C_i$ by a single operation.
• The cost of the sequence is the sum of the single-operation costs over all $0 \le i < k$.

The first line contains two integers $N$ $M$ ($1 \le N \le 40$, $0 \le M \le 16$): the number of bricks and the number of configurations to visit. Each of the next three lines contains three integers. The $j$-th integer on the $i$-th line is $R_{i,j}$ ($0 \le R_{i,j} \le 1000$, $R_{i,i} = 0$), the cost of moving one brick from Park $i$ to Park $j$. The next three lines describe the initial configuration, followed by $M$ blocks of three lines describing the desired configurations. Every configuration uses the following format.

One configuration is written in three lines. The $i$-th line starts with an integer $K$ ($0 \le K \le N$), the number of bricks in Park $i$, followed by $K$ integers $A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$) naming the bricks in Park $i$. For all $1 \le i < j \le K$, $A_i < A_j$ holds, and every integer from $1$ to $N$ appears exactly once across the three lines.

Print the minimum total cost that satisfies the governor's demand, in one line.

Explanation of the first case

In the first case, Park 1 initially holds bricks $1$ and $2$ while Park 3 holds brick $3$. Since $M = 0$, it suffices to gather all bricks into one park, which can be done with cost $5$ as follows.

• Move brick $3$ from Park 3 to Park 2. This costs $1$.
• Move brick $1$ from Park 1 to Park 2. This costs $1$.
• Move brick $1$ from Park 2 to Park 3. This costs $1$.
• Move brick $2$ from Park 1 to Park 2. This costs $1$.
• Move brick $1$ from Park 3 to Park 2. This costs $1$.

All bricks are now in Park 2 with total cost $5$, and no cheaper sequence exists. Note that the number of operations is not minimized.

Explanation of the second case

In the second case, the optimum visits the second desired configuration before the first one. From the initial configuration, the second configuration is reachable in $4$ operations with total cost $8$. From the second configuration, the first configuration is reachable in $7$ operations with total cost $14$. Since the first configuration already stacks all bricks in one park, no further operation is needed. The total cost is therefore $22$.