Buy or Build

World Wide Networks (WWN) operates large telecommunication networks and wants to build a new network in the country of Borduria that connects all $n$ of its largest cities at the smallest possible total cost.

Several local companies already run small subnetworks, each of which interconnects some of the cities. To provide connectivity, WWN may use either of two mechanisms:

• Build an edge directly between two cities. Its cost is exactly the square of the Euclidean distance between them: for cities at $(x_1, y_1)$ and $(x_2, y_2)$ the cost is $(x_1 - x_2)^2 + (y_1 - y_2)^2$.
• Buy a subnetwork. Buying subnetwork $c$ costs $w_c$ and immediately connects all cities that belong to it. A subnetwork must be bought as a whole and cannot be split.

Every city has integer coordinates. There are $q$ subnetworks, and $q$ is always small ($q \le 8$); the internal layout of a subnetwork is irrelevant, because buying it makes all of its cities mutually connected.

Choose which subnetworks to buy and which edges to build so that all $n$ cities end up connected and the total cost — the prices of the bought subnetworks plus the cost of every built edge — is minimized.

The first line contains two integers $n$ and $q$ ($1 \le n \le 1000$, $0 \le q \le 8$): the number of cities and the number of existing subnetworks. Cities are numbered from $1$ to $n$.

Each of the next $q$ lines describes one subnetwork. The line begins with an integer $m$, the number of cities in that subnetwork, then an integer $w$, its price ($w \le 2\,000\,000$), then the $m$ distinct city numbers belonging to it.

Each of the final $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 3000$): the coordinates of city $i$ (city $1$ on the first of these lines, city $2$ on the second, and so on).

Print a single integer: the minimum total cost to connect all $n$ cities.

The figures below are illustrations. The first two show a $115$-city instance with $4$ subnetworks and a solution that buys the first and third subnetworks (thick edges belong to a bought subnetwork; thin edges are built from scratch). The last two show the $7$-city instance from the example and one of its optimal solutions, in which the first and second subnetworks are bought and the remaining connecting edges are built from scratch, for a total cost of $17$.