구매 또는 건설

시간 제한1초메모리 제한128 MB

요약

최대 8개의 서브네트워크 중 일부를 사고 나머지 도시를 간선으로 이어, 모든 도시를 연결하는 최소 총비용을 구한다.

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

문제

World Wide Networks(WWN)는 대규모 통신망을 운영하는 회사로, 보르두리아(Borduria)라는 나라의 가장 큰 도시 $n$ 개를 모두 연결하는 새 통신망을 최소 비용으로 구축하려고 합니다.

이 나라에는 이미 일부 도시들을 서로 연결해 둔 작은 서브네트워크가 여러 개 있습니다. WWN이 도시들을 연결하는 방법은 두 가지입니다.

간선 건설: 두 도시를 직접 잇는 간선을 새로 만듭니다. 이 간선의 비용은 두 도시 사이 유클리드 거리의 제곱입니다. 좌표가 $(x_1, y_1)$ , $(x_2, y_2)$ 인 두 도시라면 비용은 $(x_1 - x_2)^2 + (y_1 - y_2)^2$ 입니다.
서브네트워크 구매: $c$ 번 서브네트워크를 사면 비용 $w_c$ 가 들고, 그 서브네트워크에 속한 모든 도시가 한꺼번에 연결됩니다. 서브네트워크는 통째로만 살 수 있으며 일부만 나눠 살 수는 없습니다.

모든 도시의 좌표는 정수입니다. 서브네트워크의 개수 $q$ 는 항상 작습니다( $q \le 8$ ). 서브네트워크 내부가 실제로 어떻게 연결되어 있는지는 중요하지 않습니다. 구매하기만 하면 그 안의 도시들이 모두 서로 연결된다고 봅니다.

어떤 서브네트워크를 사고 어떤 간선을 건설할지 정해서, $n$ 개 도시가 모두 연결되도록 하면서 총비용(구매한 서브네트워크 가격의 합 + 건설한 간선 비용의 합)을 최소로 만드세요.

입력

첫 줄에 도시의 수 $n$ 과 기존 서브네트워크의 수 $q$ 가 주어집니다( $1 \le n \le 1000$ , $0 \le q \le 8$ ). 도시는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다.

이어지는 $q$ 개의 줄에는 서브네트워크가 하나씩 주어집니다. 각 줄은 그 서브네트워크에 속한 도시의 수 $m$ , 가격 $w$ ( $w \le 2\,000\,000$ ), 그리고 그 서브네트워크에 속한 도시 번호 $m$ 개 순서로 이루어집니다.

마지막 $n$ 개의 줄에는 도시의 좌표가 주어집니다. $i$ 번째 줄에는 도시 $i$ 의 좌표 $x_i$ 와 $y_i$ 가 주어집니다( $0 \le x_i, y_i \le 3000$ ).

출력

모든 도시를 연결하는 데 드는 최소 총비용을 정수 하나로 출력합니다.

참고

아래 그림은 이해를 돕기 위한 예시입니다. 처음 두 그림은 서브네트워크가 $4$ 개인 $115$ 개 도시 인스턴스와, 그중 첫 번째와 세 번째 서브네트워크를 구매한 해를 보여줍니다(굵은 간선은 구매한 서브네트워크에서 온 것이고, 얇은 간선은 새로 건설한 것입니다). 마지막 두 그림은 공개 테스트로 주어진 $7$ 개 도시 인스턴스와 그 최적해 중 하나로, 첫 번째와 두 번째 서브네트워크를 구매하고 나머지 연결 간선을 새로 건설해 총비용 $17$ 을 얻습니다.

예제4

예제 1

입력

예상 출력

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