Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (Xi, Yi). Также на карте обозначены M точек с координатами (Pi, Qi), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).
Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.
Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!
Входные данные
Первая строка входных данных содержит два целых числа
N и
M (1 <= N <= 12, 0 <= M <=5). Следующие
N строк содержат координаты городов (
Xi,
Yi). Далее идут
M строк с координатами ускорителей (
Pi,
Qi). Все координаты различны и среди них нет координаты (
0,
0).
Выходные данные
Выведите ответ на задачу, с точностью не менее 6 знаков после запятой.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
2 1
1 1
0 1
1 0 |
2 1
1 1
0 1
1 0 |
Вот один из оптимальных способов разнести все подарки
- Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
- Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5.
- Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5.
- Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
|
| 2 |
2 1
1 1
0 1
100 0 |
3.4142135624 |
Вот один из оптимальных способов разнести все подарки
- Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41....
- Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1.
- Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
|
| 3 |
1 2
4 4
1 0
0 1 |
4.3713203436 |
Вот один из оптимальных способов разнести все подарки
- Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
- Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707....
- Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25.
- Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....
|