Problem J
Fencing Lessons
Donald’s garden has $N$ trees and $M$ poles that he has erected in strategic locations on integer meter coordinates. He wants to start breeding squirrels on top of these poles. Unfortunately there are lots of dangerous predators in the area, so if he leaves the poles unprotected, they will eat all of the squirrels. In order to keep the squirrels safe, he has decided to build a single, connected fence around the poles. As we all know, it is not possible to breed squirrels if all the poles are placed on a single line, so Donald has made sure to avoid this.
Building a fence is hard work, so he wants to build the fence as short as possible, while still completely enclosing all the poles. The poles are so thin that they can be considered points.
In order to build the fence, he has to cut down some trees and make boards to build it from. For each of the trees in the garden, he knows both how many meters ($m$) of boards he gets, and how long it will take him to do it ($t$). Donald wants to start breeding squirrels as soon as possible, so he is also in a hurry. Help Donald figure out which trees to use to build his fence as quickly as possible.
Input
The input starts with a line with two space-separated integers $N$ and $M$.
The next $N$ lines each consists of two space-separated integers $m_ i$ and $t_ i$ describing the $i^{\text {th}}$ tree.
The next $M$ lines each consists of two space-separated integers $x_ i$ and $y_ i$ describing the coordinates of the $i^{\text {th}}$ pole’s position.
Output
Output the minimum amount of time it takes to produce the boards necessary for the fence.
Limits
-
$1 \leq N \leq 1\, 000$
-
$3 \leq M \leq 1\, 000$
-
$1 \leq m_ i, t_ i \leq 1\, 000$
-
$0 \leq x_ i, y_ i \leq 1\, 000$
-
$\sum \limits _{i=1}^ N m_ i$ will always be large enough to build the fence.
-
No two poles will have the same coordinates.
-
The length of the fence will not be within $10^{-6}$ of an integer.
-
The positions of the poles will not all be colinear.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 4 10 2 4 2 4 0 0 0 1 1 0 |
8 |
