URI Online Judge | 2810

Dengue 2.0

By Gabriel Duarte, UFF BR Brazil

Timelimit: 1

As you may recall* John was trying to break the focus of dengue in his city, but this task was not so simple because of the number of places he should visit. So he asked the help of his friends to solve this problem.

You will be given all the focus of dengue, which can be seen as coordinates in the cartesian plane and the coordinate of all houses, of John and his friends. What has been decided is that all focus of dengue should be visited exactly once and at the end all participants should return to their respective homes.

Can you tell John beforehand what is the minimum distance traveled by all friends to visit all the outbreaks?

John is a smart guy, so he knows there may be cases where the help of all his friends will not be needed.

Input

The first line of each test case will have two integers N and M (1 ≤ N ≤ 10, 1 ≤ M ≤ 5), representing the number of dengue focus on the map and how many people will participate in the mission, including John, respectively. It follows M lines containing two integers X and Y (-100 ≤ X, Y ≤ 100), representing the coordinate of one of the houses. Then there will be N lines, each containing two integers X and Y (-100 ≤ X, Y ≤ 100), representing the coordinate of a dengue focus.

Output

Print the minimum amount that will be covered by John and his friends.

Input Sample Output Sample

4 1
0 0
1 2
2 3
2 2
3 3

8.89

4 2
-1 -1
0 0
1 2
2 3
2 2
3 3 
 

8.89