eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Кухонний робот

Кухонний робот

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Роботи з часом стають все популярнішим. Сьогодні їх використовують не лише на великих заводах, але і в домашніх умовах. Один програміст разом зі своїми друзями вирішили створити свого власного домашнього робота. Як Ви знаєте, більшість програмістів полюбля збиратись по вечерам і пити пиво. Після завершення цього дійства на столі зажається безліч пустих пляшок. Тому було вирішено створти робота, який буде здатним зібрати пусті пляшки зі столу.

Стіл являє собою прямокутник з довжиною 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}.

Приклад

Вхідні дані #1
3 4
2
1 1
2 3
2 1
Вихідні дані #1
5.60555127546399
Автор Fedor Tsarev
Джерело 2010 ACM NEERC, Northern Subregion, October 30, Problem K