The mayor of the Sky-Dragon city, Mr. Good, would like to build a monorail trolley system to promote the tourism industry.
There are N scenic sites in the city, and Mr. Good would like all of them to be connected by the monorails.
Furthermore, there are Q optional sites which Mr. Good may want to include some of them.
These Q sites are ordered decreasingly by the interestingness,
so Mr. Good may choose to include first-q of them, where 0<= q <= Q.
You are asked to calculate the minimum cost of each possible choice.
The cost to build the monorails is 1 million dollars per kilometer.

The rails have to be built along the existing roads in the city.
The Sky-Dragon city is well designed so that all the roads run north-south or east-west.
The north-south roads are called avenues, numbered from 1 (west-most) to X (east-most).
Similarly, the east-west roads are called streets, numbered from 1 (south-most) to Y (north-most).
Two neighboring avenues are 1 kilometer apart, so as two neighboring streets.
All the scenic sites are located at the intersection of a street and an avenue.
We would use (x,y) to denote the intersection of the x-th avenue and the y-th street.

There will be one station at each scenic site, and no other station will be built.
Due to the high cost and technical difficulties, there should not be any switches on the rails.
That is, each monorail line should connect two stations directly,
and two monorail lines cannot share any piece of rails, even if they lie on the same road.
However, it is allowed to have two or more rails on the same road, since they can be differentiated vertically.

Now, given N, Q, and the locations of the sites, please calculate the minimum cost of Q+1 possible choices.