Santa Claus must visit N cities overnight. He has a two-dimensional plan for the location of all cities. The plan is drawn in Cartesian system of coordinates, in which point (0, 0) indicates the place where Father Frost starts. Each city on the plan is marked with a point with the coordinate ;(Xi, Yi). Also on the map are marked M points with coordinates (Pi, Qi) , in which accelerators are located. In order to have time to deliver all the gifts, Santa Claus can use an accelerator that doubles his speed (or maybe not use it).
On New Year's Eve Santa Claus starts from the starting point, visits all N cities and returns.
Father Frost's initial speed is 1. Find the shortest time it takes for Santa Claus to visit all the cities and return back. We will neglect the time at which he lays out all the gifts!
Input
The first line of the input contains two integers
N and
M (1 <= N <= 12, 0 <= M <=5). The following
N lines contain the coordinates of cities (
Xi,
Yi). Then there are
M lines with accelerator coordinates (
Pi,
Qi). All coordinates are different and there is no (
0,
0).
Imprint
Print the answer to the problem, with an accuracy of at least 6 decimal places.
Examples
| # |
Input |
Output |
Note |
| 1 |
2 1
1 1
0 1
10 |
2 1
1 1
0 1
10 |
Here is one of the best ways to distribute all the gifts
- Move distance 1 from the origin to accelerator 1 at speed 1, spending time 1.
- Move distance 1 from accelerator 1 to city 1 at speed 2 in time 0.5.
- Travel distance 1 from city 1 to city 2 at speed 2, taking time 0.5.
- Travel distance 1 from city 2 to origin at speed 2 in time 0.5.
|
| 2 |
2 1
1 1
0 1
1000 |
3.4142135624 |
Here is one of the best ways to distribute all the gifts
- Travel distance 1.41... from origin to city 1 at speed 1, spending time 1.41....
- Travel distance 1 from city 1 to city 2 at speed 1, spending time 1.
- Travel distance 1 from city 2 to the origin at speed 1, spending time 1.
|
| 3 |
1 2
4 4
10
0 1
| 4.3713203436 |
Here is one of the best ways to distribute all the gifts
- Move distance 1 from the origin to accelerator 1 at speed 1, spending time 1.
- Move distance 1.41... from accelerator 1 to accelerator 2 at speed 2, spending time 0.707....
- Move distance 5 from accelerator 2 to city 1 at speed 4 in time 1.25.
- Travel distance 5.65... from city 1 to origin at speed 4, spending time 1.41....
|