Задача: Ускорители для Деда Мороза

Дед Мороз за ночь должен посетить 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....

           

Ваш ответ: