题目描述

雅加达有三个公园，分别称为公园 $1$、公园 $2$ 和公园 $3$。

雅加达的新任州长希望通过摆放砖块来装饰这些公园。砖块会在三个公园中分别堆成若干堆。

共有 $N$ 块砖，编号为 $1$ 到 $N$。编号为 $i$ 的砖比编号为 $i+1$ 的砖小。

不能把较大的砖放在较小的砖上。因此，编号为 $i$ 的砖可以放在编号为 $j$ 的砖上，当且仅当：

$$i<j.$$

定义一种砖块状态为：将全部砖块分配到三个公园中，并满足：

• 每个公园中至多有一摞砖；
• 每摞砖都符合上述大小顺序。

例如，当 $N=3$ 时，一种合法状态是：

• 公园 $1$ 中，砖块 $1$ 在砖块 $2$ 上方；
• 公园 $2$ 中没有砖；
• 公园 $3$ 中放置砖块 $3$。

可以通过一次操作把一种状态变成另一种状态。一次操作如下：

1. 选择两个不同的公园 $i$ 和 $j$；
2. 取出公园 $i$ 最上方的砖块，并放到公园 $j$ 的最上方。

若公园 $i$ 中没有砖，则该操作非法。

若移动后公园 $j$ 中的砖块顺序不合法，则该操作同样非法。

把一块砖从公园 $i$ 运到公园 $j$ 需要支付 $R_{i,j}$ 单位费用。运输费用可能不对称，即：

$$R_{i,j}$$

不一定等于

$$R_{j,i}.$$

初始时，砖块处于某个给定的初始状态。

州长希望依次观察若干指定状态。你可以自行决定访问这些指定状态的顺序，但每一个指定状态都必须至少出现一次。

完成这些要求后，还必须把所有砖块集中到任意一个公园中。

请计算满足全部要求所需的最小总费用。

更形式化地，给定州长要求访问的状态：

$$G_1,G_2,\ldots,G_M.$$

需要构造状态序列：

$$C_0,C_1,\ldots,C_k\qquad(k\ge0),$$

使得：

• $C_0$ 是初始状态；
• 对每个 $1\le i\le M$，至少存在一个下标 $x_i$，满足 $C_{x_i}=G_i$；
• $C_k$ 中全部砖块位于同一个公园；
• 对每个 $0\le i<k$，可以通过一次合法操作从 $C_i$ 变为 $C_{i+1}$；
• 总费用最小。

指定状态的访问顺序不受输入顺序限制。

输入格式

第一行包含两个整数 $N,M$：

$$1\le N\le40,\qquad 0\le M\le16,$$

分别表示砖块数量和州长要求访问的状态数量。

接下来三行，每行包含三个整数。第 $i$ 行的第 $j$ 个整数为 $R_{i,j}$，表示从公园 $i$ 向公园 $j$ 搬运一块砖的费用。

满足：

$$0\le R_{i,j}\le1000,$$

并且：

$$R_{i,i}=0.$$

随后用三行描述初始状态。第 $i$ 行的格式为：

K b1 b2 ... bK

表示公园 $i$ 中有 $K$ 块砖，从上到下依次为：

$$b_1,b_2,\ldots,b_K.$$

当 $K=0$ 时，该行只包含一个 0。

保证：

$$0\le K\le N,$$

每一摞砖的编号严格递增，并且 $1$ 到 $N$ 的每块砖在三个公园中恰好出现一次。

接下来依次描述 $M$ 个州长要求访问的状态。每个状态同样由三行组成，格式与初始状态完全相同。

输出格式

输出一个整数，表示满足全部要求所需的最小总费用。

样例 1

输入

3 0
0 1 1000
1 0 1
1000 1 0
2 1 2
0
1 3

输出

5

样例 2

输入

3 2
0 2 2
2 0 2
2 2 0
2 1 2
1 3
0
3 1 2 3
0
0
0
0
3 1 2 3

输出

22