Fence

Time limit1sMemory limit128 MB

Summary
Choose a subset of given points to form a convex polygon fence minimizing 20 times the number of posts used plus 111 times the number of trees left outside, considering all possible fences.
Level

Hard8 of 10

Topics
Geometry, Dynamic programming, Brute force
Solved
No attempts yet

Problem

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.

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. 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

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.

Examples4

  1. Example 1

    Input
    4 3
800 300
200 200
200 700
600 700
400 300
600 500
800 900
    Expected output
    171

  2. Example 2

    Input
    3 1
0 0
10 0
5 10
5 3
    Expected output
    60

  3. Example 3

    Input
    3 1
0 0
10 0
5 10
100 100
    Expected output
    111

  4. Example 4

    Input
    3 6
0 0
1000 0
0 1000
137 241
452 88
211 509
613 152
88 701
305 333
    Expected output
    60