CEOI08A - Fences

no tags 

One morning, fruit farmer Fred visits his apple trees and notices that one of them was cut overnight. This means a loss of 111e – the money he can make from the apples of a tree on average. In order to prevent further losses, he decides to erect a fence on his plantation. The fence consists of posts connected by wire.

The fence posts can only be placed at a given set of pre-drilled holes. While Fred can get wire for free, he needs to buy the fence posts for 20e each. So it might not always be worth or even possible to fence in all of his trees.

fences

The plantation is square and 1 000 × 1 000 m2 large. In bird’s eye view, the lower left corner has coordinates (0, 0), the upper right (1 000, 1 000). In this example there are four pre-drilled holes (circles) and three trees (squares). It is optimal to buy three fence posts and put them into selected holes (filled circles), to connect them by wire (lines), and to leave the upper left hole empty. The cost of erecting the fence is 3 × 20e + 1 × 111e = 171e since three posts were bought and one tree could not be fenced in (which means a loss of that tree’s harvest).

Write a program that reads the positions of the pre-drilled holes and the trees on Fred’s plan-tation and outputs the minimum cost of erecting a fence or erecting no fence at all. You can neglect the actual shape of the trees and calculate with their positions only.

Input

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. This line is followed by N lines that describe the positions of the holes, and then by M lines that describe the positions of the trees. Allpositions are given as pairs of integers x y on one line (0 ≤ x, y ≤ 1 000). You can expect that no two positions (of holes and trees) coincide and that no three positions are colinear.

Output

Output a single line containing one integer: Fred’s minimum cost. In case Fred buys P posts and fails to fence in T trees, his cost are 20 × P + 111 × T.

Example

Input:
4 3
800 300
200 200
200 700
600 700
400 300
600 500
800 900

Output:
171

This example corresponds to the picture above.

(Official Test Data)


hide comments
Szymon: 2015-05-15 23:12:34

can somebody provide me with tests??
my code gives good answers for all tests from
http://ceoi.inf.elte.hu/probarch/08/all.zip


Added by:Shafaet
Date:2012-12-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:15th Central Europe Olympiad in Informatics, Germany