0 人解决，3 人已尝试。
0 份提交通过，共有 10 份提交。
9.9 EMB 奖励。
2579. Fence
单点时限: 2.0 sec
内存限制: 256 MB
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.
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 plantation 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.
输入格式
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. All positions are given as pairs of integers xy 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 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 20P + 111T .
样例
Input
4 3 800 300 200 200 200 700 600 700 400 300 600 500 800 900
Output
171
题目标签