동물 농장

시간 제한2초메모리 제한512 MB

요약

여러 우리가 벽을 공유하며 배치되어 있을 때, 모든 동물이 한 우리 안이나 우리 밖 한 영역에 모이도록 벽을 허무는 최소 비용을 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 최소 신장 트리, 유니온 파인드, 그리디
정답자: 아직 제출이 없습니다

문제

농장에 $N$ 마리( $1 \le N \le 100$ )의 동물이 있고, 상점에서 동물을 넣을 미리 만들어진 우리 $M = N$ 개를 사 왔습니다. 우리는 다음 조건을 만족합니다.

각 우리는 $3$ 개 이상 $8$ 개 이하의 변(벽)을 가진다.
두 우리에 공통으로 나타나는 변은 그 두 우리를 서로 맞닿게 연결한다.
한 우리에만 나타나는 변은 그 우리를 바깥(모든 우리의 외부)과 연결한다.
처음에 각 우리 안에는 정확히 한 마리의 동물이 있고, 우리 밖에는 동물이 없다.

동물들은 "우리 탈출"이라는 놀이를 즐깁니다. 각 변에는 비용이 정해져 있고, 동물들은 여러 우리의 벽을 밟아 부수어 모든 동물이 같은 구역에 모이는 데 드는 최소 비용을 구하려 합니다. 동물들은 특정한 우리 안에서 모일 수도 있고, 모든 우리의 바깥에서 모일 수도 있습니다. 한 번 밟아 부순 변은 그 이후로 어떤 동물이든 추가 비용 없이 지나갈 수 있습니다.

우리의 구조와 동물의 배치가 주어질 때, 모든 동물을 같은 구역으로 모으는 데 드는 최소 비용을 구하세요.

입력

첫째 줄에 우리의 개수를 나타내는 정수 $M$ 이 주어진다. 이어지는 $M$ 개의 줄에 각 우리에 대한 설명이 한 줄에 하나씩 주어진다. 각 설명은 공백으로 구분된 세 부분으로 이루어진다.

첫 번째 부분은 정수 $e_p$ ( $3 \le e_p \le 8$ )로, 우리 $p$ 의 변의 개수이다.
두 번째 부분은 $e_p$ 개의 정수로, 우리의 꼭짓점을 나타낸다. 각 정수는 $1000$ 이하이다.
세 번째 부분은 $e_p$ 개의 정수로, 각 변의 비용을 나타낸다. 각 정수는 $5000$ 이하이다.

꼭짓점과 변의 비용은 순환(cyclic) 순서로 주어진다. 예를 들어 다음과 같은 우리 설명

3 1 2 3 7 4 6

은 꼭짓점이 $3$ 개(따라서 변도 $3$ 개)이며, 변 $(1, 2)$ 의 비용이 $7$ , 변 $(2, 3)$ 의 비용이 $4$ , 변 $(3, 1)$ 의 비용이 $6$ 임을 뜻한다.

출력

모든 동물이 하나의 우리 안 또는 모든 우리의 바깥에 모이도록 하는 최소 비용을 한 줄에 출력한다.

예제3

예제 1

입력

4
3 1 2 3 7 4 6
4 1 2 4 5 7 7 2 6
4 4 7 6 5 4 8 9 2
5 3 2 4 7 8 4 7 4 7 7

예상 출력

예제 2
입력
```
1
3 1 2 3 5 5 5
```
예상 출력
```
0
```
예제 3
입력
```
2
3 1 2 3 10 20 30
3 1 2 4 10 5 5
```
예상 출력
```
10
```