雅加达有三个公园，分别称为公园 1、公园 2 和公园 3。雅加达的新任总督想要通过添加砖块来装饰这些公园。这些砖块将堆叠在三个公园中。雅加达共有 $N$ 块砖，编号从 1 到 $N$。编号为 $i$ 的砖块比编号为 $i+1$ 的砖块小。我们不希望把较大的砖块放在较小的砖块上面。因此，仅当 $i < j$ 时，我们才能将编号为 $i$ 的砖块放在编号为 $j$ 的砖块上面。
我们将砖块在三个公园中的分布定义为一种砖块配置。注意，每个公园中必须只有一个砖块堆，且砖块必须按照上一段所述的顺序堆叠。例如，如果 $N=3$，一种可能的砖块配置是：砖块 1（在顶部）和砖块 2（在底部）位于公园 1，公园 2 中没有砖块，砖块 3 位于公园 3。
我们可以通过执行以下操作将一种砖块配置更改为另一种： 选择两个不同的公园 $i$ 和 $j$。取出公园 $i$ 堆栈中最顶部的砖块，并将其放在公园 $j$ 堆栈的顶部。如果公园 $i$ 中没有砖块，则此操作无效。如果此操作导致公园 $j$ 的堆栈违反了堆叠顺序条件，则此操作也无效。 由于我们需要租用卡车将砖块从公园 $i$ 运输到公园 $j$，我们需要为该操作支付 $R_{i,j}$ 单位的费用。注意，将砖块从公园 $i$ 运输到公园 $j$ 的费用可能与从公园 $j$ 运输到公园 $i$ 的费用不同。
最初，砖块处于某种砖块配置中，我们称之为初始砖块配置。雅加达的新任总督想要尝试 $M$ 种砖块配置。因此，我们必须从初始砖块配置开始执行若干操作，使得新任总督想要的每种砖块配置（以任意顺序）至少出现一次。最后，新任总督还希望我们将所有砖块都放在（任意）一个公园中。我们希望最小化满足其需求的总成本。
形式化地说，令 $G_1, G_2, \dots, G_M$ 为新任总督想要的砖块配置。我们想要构建一个砖块配置序列 $C_0, C_1, \dots, C_k$ ($k \ge 0$)，使得总成本最小，其中： $C_0$ 是初始砖块配置。 存在一个整数序列 $x_1, x_2, \dots, x_M$ ($0 \le x_i \le k$)，使得 $\{C_{x_1}, \dots, C_{x_M}\} = \{G_1, \dots, G_M\}$。注意，该序列不一定是递增的。 $C_k$ 是一种所有砖块都堆叠在（任意）一个公园中的砖块配置。 对于所有 $0 \le i < k$，我们可以通过执行一次操作（如上所述）从 $C_i$ 达到 $C_{i+1}$。 * 该序列的成本是所有 $0 \le i < k$ 更改 $C_i$ 到 $C_{i+1}$ 所需费用的总和。
让我们帮助雅加达的新任总督！
输入格式
第一行包含两个整数：$N$ ($1 \le N \le 40$) 和 $M$ ($0 \le M \le 16$)，分别表示砖块的数量和配置的数量。接下来的三行，每行包含三个整数。第 $i$ 行的第 $j$ 个整数是 $R_{i,j}$ ($0 \le R_{i,j} \le 1000$; $R_{i,i} = 0$)，表示将砖块从第 $i$ 个公园移动到第 $j$ 个公园的费用。接下来的三行表示初始砖块配置，格式如下文所述。接下来的 $M$ 个块描述了新任总督想要的配置，每个块包含三行，格式与下文所述相同。
每种配置由三行表示。第 $i$ 行以一个整数 $K$ ($0 \le K \le N$) 开头，表示公园 $i$ 中的砖块数量，后跟 $K$ 个整数：$A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$)，表示公园 $i$ 中的砖块编号。保证对于所有 $1 \le i < j \le K$，都有 $A_i < A_j$。还保证 1 到 $N$ 之间的每个整数在三行数组 $A$ 的并集中恰好出现一次。
输出格式
输出一行，包含满足新任总督需求所需的最小总成本（以货币单位计）。
样例
样例输入 1
3 0 0 1 1000 1 0 1 1000 1 0 2 1 2 0 1 3
样例输出 1
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
样例输出 2
22
说明
样例 1 说明
在第一个样例中，我们最初在公园 1 有砖块 1 和砖块 2，在公园 3 有砖块 3。由于 $M=0$，我们的目标只是达到一种所有砖块都在同一个（任意）公园的砖块配置。因此，我们可以执行以下操作： 将砖块 3 从公园 3 移到公园 2。费用为 1。 将砖块 1 从公园 1 移到公园 2。费用为 1。 将砖块 1 从公园 2 移到公园 3。费用为 1。 将砖块 2 从公园 1 移到公园 2。费用为 1。 * 将砖块 1 从公园 3 移到公园 2。费用为 1。
因此，所有砖块现在都在公园 2，我们花费了 5 个单位的费用。没有比 5 个单位费用更低的方案。注意，我们不一定需要最小化操作次数。
样例 2 说明
在第二个样例中，如果我们先满足第二个配置，再满足第一个配置，就可以达到最优解。从初始配置出发，我们可以用 4 次操作达到第二个配置，总成本为 8。从第二个配置出发，我们可以用 7 次操作达到第一个配置，总成本为 14。由于第一个配置已经将所有砖块堆叠在一个公园中，我们不需要任何额外的操作。因此，总成本为 22。