Кухонний робот#2268
Роботи з часом стають все більш популярними. Сьогодні їх використовують не тільки на великих заводах, але й у побуті. Один програміст разом з друзями вирішив створити власного домашнього робота. Як відомо, багато програмістів люблять збиратися на вечірки і пити пиво. Після таких вечірок стіл зазвичай виявляється заставленим порожніми пляшками. Тому вони вирішили зробити робота, який зможе збирати порожні пляшки зі столу.
Стіл є прямокутником довжини і ширини . Робот стартує з точки (x_r, y_r), а пляшок розташовані в точках (x_i, y_i), де 1 \le i \le n. Щоб підібрати пляшку, робот має підійти до неї, захопити її, а потім донести до якоїсь точки на межі столу і відпустити. У будь-який момент робот може нести тільки одну пляшку та може залишити її тільки на межі столу.
Розміри пляшок і робота можна вважати знехтованими (і робот, і пляшки — точки). Робот, котрий несе пляшку, може проходити через точки, у яких знаходяться інші пляшки.
Один з модулів робота займається побудовою маршруту. Вам потрібно написати програму, яка визначає найкоротший можливий маршрут, яким робот зможе зібрати всі пляшки.
У першому рядку задано два цілі числа і l~(2 \le w, l \le 1000) — ширина і довжина столу.
У другому рядку задано число пляшок n~(1 \le n \le 18). У наступних рядках містяться по два цілі числа x_i, y_i~(0 < x_i < w, 0 < y_i < l) — координати -ої пляшки. Жодні дві пляшки не розташовані в одній точці.
У останньому рядку дані два цілі числа x_r, y_r~(0 < x_r < w, 0 < y_r < l) — координати стартової позиції робота. Робот не знаходиться в одній точці з жодною з пляшок.
Виведіть довжину найкоротшого маршруту, яким робот збирає всі пляшки. Помилка обчислення не повинна перевищувати 10^{-6}.
Приклад 1