Fence

One morning, fruit farmer Fred visits his apple trees and finds that one of them was cut down overnight. On average each tree is worth 111€ — the money Fred earns from the apples of one tree. To prevent further losses, he decides to build a fence on his plantation.

The fence is made of posts connected by wire. Posts may only be placed in a given set of pre-drilled holes. Wire is free, but each post costs 20€, so it may not always be worth it — or even possible — to fence in all of the trees.

The plantation is a square of 1000×1000 m². In bird's-eye view, the lower-left corner is at (0, 0) and the upper-right corner is at (1000, 1000).

For instance, suppose there are four pre-drilled holes (circles) and three trees (squares). The best choice is to buy three posts, place them in selected holes (filled circles), connect them with wire (lines), and leave the upper-left hole empty. The cost is then 3·20€ + 1·111€ = 171€, because three posts were bought and one tree could not be fenced in (a loss of that tree's harvest).

Write a program that reads the positions of the pre-drilled holes and the trees and outputs the minimum total cost — where building no fence at all is also an option. Treat each tree as a single point and ignore its actual shape.

The first line contains two integers N and M (3 ≤ N ≤ 100, 1 ≤ M ≤ 100): N is the number of pre-drilled holes and M is the number of trees. The next N lines give the positions of the holes, and the following M lines give the positions of the trees. Each position is a pair of integers x y on one line (0 ≤ x, y ≤ 1000). No two positions coincide, and no three positions are collinear.

Output a single line with one integer: Fred's minimum cost. If Fred buys P posts and fails to fence in T trees, his cost is 20·P + 111·T.