구매 또는 건설

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$을 얻습니다.