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