판다 나라 5: 판다 프로그래밍 언어

판다 세계에는 프로그래밍 언어가 단 하나뿐이며, 그 이름은 판다 프로그래밍 언어(PPL)이다. PPL은 절차적 언어여서 하나의 프로그램 안에 여러 개의 함수를 정의할 수 있고, 재귀 호출(함수가 자기 자신을 호출하는 것)도 허용된다.

PPL에는 함수 원형(prototype) 선언 기능이 없다. 따라서 모든 함수는 자신을 호출하는 다른 함수보다 먼저 정의되어 있어야 한다. 즉, 함수 $A$가 함수 $B$를 호출한다면($B \ne A$), 소스 파일에서 $B$가 $A$보다 위에 있어야 한다.

어떤 프로그램이 이 순서를 고려하지 않고 작성되어, 일부 함수가 자신을 호출하는 함수보다 뒤에 정의되어 있어 컴파일되지 않는다. 당신의 임무는 프로그램이 컴파일되도록 함수들의 순서를 재배치하되, 총 재배치 비용을 최소화하는 것이다.

함수 하나를 옮기는 비용은 그 함수의 줄 수에 건너뛴 줄의 총합을 곱한 값이다. 예를 들어 위에서 아래로 놓인 네 함수 $A, B, C, D$의 줄 수가 각각 $10, 4, 6, 3$이라고 하자. $A$를 $D$ 아래로 옮기면 $B, C, D$를 건너뛰므로 비용은 $10 \times (4 + 6 + 3) = 130$이다. $D$를 $A$와 $B$ 사이로 올리면 $C, B$를 건너뛰므로 비용은 $3 \times (6 + 4) = 30$이다.

프로그램이 컴파일되는 순서로 함수들을 재배치하는 최소 총비용을 구하라. 함수가 자기 자신을 호출하는 것은 허용되므로 자기 참조는 컴파일을 막지 않으며, 서로 다른 두 개 이상의 함수가 이루는 호출 순환이 있을 때에만 컴파일이 불가능하다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 함수의 개수 $N$ ($1 \le N \le 18$)이 주어진다. 다음 줄에는 $N$개의 정수가 주어지며, $i$번째 정수 $M_i$ ($1 \le M_i \le 100$)는 함수 $i$의 줄 수이다.

이어지는 $N$개의 줄은 함수들의 호출 관계를 나타낸다. 그중 $i$번째 줄은 정수 $C$ ($0 \le C < N$)로 시작하며, 이는 함수 $i$가 호출하는 함수의 개수이다. 그 뒤에 함수 $i$가 호출하는 함수들을 나타내는 $C$개의 정수 $F_j$ ($1 \le F_j \le N$)가 주어진다. 함수는 자기 자신을 포함할 수도 있다(재귀 호출).

각 테스트 케이스의 마지막 줄에는 $N$개의 정수가 주어지며, 이는 함수들의 초기 배치 순서(위에서 아래로)를 나타내는 $1 \dots N$의 순열이다.

각 테스트 케이스마다 프로그램이 컴파일되도록 재배치하는 최소 비용을 한 줄에 출력한다. 유효한 배치가 존재하지 않으면 $-1$을 출력한다.