자카르타의 공원

자카르타에는 1번 공원, 2번 공원, 3번 공원이라는 세 개의 공원이 있다. 자카르타의 새 주지사는 이 공원들에 벽돌을 쌓아 장식하려고 한다. 자카르타에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 벽돌이 있으며, 번호가 작을수록 작은 벽돌이다. 작은 벽돌 위에는 큰 벽돌을 올릴 수 없으므로, 벽돌 $j$ 위에 벽돌 $i$를 올릴 수 있는 경우는 $i < j$인 경우뿐이다.

벽돌 배치란 $N$개의 벽돌을 세 공원에 나누어 쌓은 상태를 뜻한다. 각 공원에는 최대 하나의 벽돌 더미만 있어야 하며, 모든 더미는 위의 규칙을 따라야 한다. 예를 들어 $N = 3$일 때, 1번 공원에 벽돌 $1$(위)과 벽돌 $2$(아래)가 있고, 2번 공원은 비어 있고, 3번 공원에 벽돌 $3$이 있는 배치가 가능하다.

배치는 다음 연산을 반복하여 바꿀 수 있다.

• 서로 다른 두 공원 $i$와 $j$를 고른다. $i$번 공원 더미의 맨 위 벽돌을 $j$번 공원 더미의 맨 위로 옮긴다. $i$번 공원이 비어 있으면 이 연산은 불가능하고, 옮긴 뒤 $j$번 공원의 쌓기 규칙이 깨지면 이 연산 역시 불가능하다.
• 벽돌을 옮기려면 트럭을 빌려야 하므로, $i$번 공원에서 $j$번 공원으로 벽돌 하나를 옮길 때마다 $R_{i,j}$만큼의 비용을 낸다. $i$번 공원에서 $j$번 공원으로 옮기는 비용과 반대 방향 비용은 다를 수 있다.

처음에는 주어진 초기 배치에서 시작한다. 주지사는 정해진 $M$개의 배치를 순서에 상관없이 각각 적어도 한 번씩 보고 싶어 한다. 마지막에는 모든 벽돌이 하나의 공원에 모여 있어야 한다. 주지사의 요구를 만족하는 총비용의 최솟값을 구하라.

형식적으로, 주지사가 보고 싶어 하는 배치를 $G_1, G_2, \dots, G_M$이라 하자. 다음 조건을 만족하는 배치 수열 $C_0, C_1, \dots, C_k$ ($k \ge 0$) 중 비용이 최소인 것을 찾는다.

• $C_0$은 초기 배치이다.
• 보고 싶어 하는 모든 배치 $G$에 대해 $C_x = G$인 정수 $x$ ($0 \le x \le k$)가 존재한다. 방문 순서는 상관없다.
• $C_k$에서는 모든 벽돌이 하나의 공원에 쌓여 있다.
• 모든 $0 \le i < k$에 대해 $C_{i+1}$은 $C_i$에 연산을 한 번 적용하여 얻을 수 있다.
• 이 수열의 비용은 모든 $0 \le i < k$에 대한 $C_i$에서 $C_{i+1}$로의 변경 비용의 합이다.

첫째 줄에 벽돌의 개수와 보고 싶은 배치의 개수인 두 정수 $N$ $M$ ($1 \le N \le 40$, $0 \le M \le 16$)이 주어진다. 다음 세 줄에는 각 줄에 세 개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $i$번 공원에서 $j$번 공원으로 벽돌 하나를 옮기는 비용 $R_{i,j}$ ($0 \le R_{i,j} \le 1000$, $R_{i,i} = 0$)이다. 다음 세 줄에는 초기 배치가 주어지고, 이어지는 $M$개의 블록에는 주지사가 보고 싶어 하는 배치가 주어진다. 각 블록은 세 줄로 이루어지며, 하나의 배치는 다음 형식으로 적는다.

하나의 배치는 세 줄로 적히며, $i$번째 줄은 $i$번 공원의 벽돌 개수인 정수 $K$ ($0 \le K \le N$)로 시작하고, 뒤이어 $i$번 공원의 벽돌 번호를 뜻하는 $K$개의 정수 $A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$)가 주어진다. 모든 $1 \le i < j \le K$에 대해 $A_i < A_j$가 보장되며, $1$부터 $N$까지의 모든 정수는 세 줄에 합쳐서 정확히 한 번씩 등장한다.

주지사의 요구를 만족하는 최소 총비용을 한 줄에 출력한다.

첫 번째 경우에 대한 설명

첫 번째 경우에서는 처음에 1번 공원에 벽돌 $1$과 벽돌 $2$가 있고 3번 공원에 벽돌 $3$이 있다. $M = 0$이므로 모든 벽돌을 하나의 공원에 모으기만 하면 되며, 예를 들어 다음 연산들로 비용 $5$에 달성할 수 있다.

• 벽돌 $3$을 3번 공원에서 2번 공원으로 옮긴다. 비용은 $1$이다.
• 벽돌 $1$을 1번 공원에서 2번 공원으로 옮긴다. 비용은 $1$이다.
• 벽돌 $1$을 2번 공원에서 3번 공원으로 옮긴다. 비용은 $1$이다.
• 벽돌 $2$를 1번 공원에서 2번 공원으로 옮긴다. 비용은 $1$이다.
• 벽돌 $1$을 3번 공원에서 2번 공원으로 옮긴다. 비용은 $1$이다.

이제 모든 벽돌이 2번 공원에 있으며 총비용은 $5$이다. $5$보다 적은 비용으로는 불가능하다. 연산 횟수를 최소화할 필요는 없음에 유의하라.

두 번째 경우에 대한 설명

두 번째 경우에서는 두 번째로 원하는 배치를 먼저 만족한 뒤 첫 번째 배치를 만족하는 것이 최적이다. 초기 배치에서 두 번째 배치까지는 $4$번의 연산으로 총비용 $8$에 도달할 수 있다. 두 번째 배치에서 첫 번째 배치까지는 $7$번의 연산으로 총비용 $14$에 도달할 수 있다. 첫 번째 배치는 이미 모든 벽돌이 하나의 공원에 모여 있으므로 추가 연산이 필요 없다. 따라서 총비용은 $22$이다.