Mətbəx robotu#2268
Robotlar zamanla daha da populyarlaşır. Bu gün onları yalnız böyük zavodlarda deyil, həm də evdə istifadə edirlər. Bir proqramçı dostları ilə birlikdə öz ev robotunu yaratmağa qərar verdi. Məlum olduğu kimi, bir çox proqramçılar partilərdə toplaşaraq pivə içməyi sevirlər. Belə partilərdən sonra masa adətən boş butulkalarla dolu olur. Buna görə onlar masanın üzərindəki boş butulkaları toplaya bilən robot düzəltməyə qərar verdilər.
Masa uzunluğu və eni olan düzbucaqlıdır. Robot (x_r, y_r) nöqtəsindən başlayır, və butulka (x_i, y_i) nöqtələrində yerləşir, burada 1 \le i \le n. Butulkanı götürmək üçün robot ona yaxınlaşmalı, onu tutmalı, sonra masanın kənarında hansısa nöqtəyə aparmalı və buraxmalıdır. Robot hər an yalnız bir butulka daşıya bilər və onu yalnız masanın kənarında buraxmalıdır.
Butulkaların və robotun ölçüləri əhəmiyyətsiz dərəcədə kiçik hesab edilə bilər (həm robot, həm də butulkalar – nöqtələrdir). Butulkaları daşıyan robot, digər butulkaların olduğu nöqtələrdən keçə bilər.
Robot modullarından biri marşrutun qurulması ilə məşğuldur. Sizdən tələb olunan, robotun bütün butulkaları toplaya biləcəyi ən qısa marşrutu müəyyən edən proqram yazmaqdır.
Birinci sətirdə iki tam ədəd və l~(2 \le w, l \le 1000) — masanın eni və uzunluğu verilir.
İkinci sətirdə butulkaların sayı n~(1 \le n \le 18) verilir. Növbəti sətirdə iki tam ədəd x_i, y_i~(0 < x_i < w, 0 < y_i < l) — -ci butulkanın koordinatları var. İki butulka eyni nöqtədə yerləşmir.
Sonuncu sətirdə iki tam ədəd x_r, y_r~(0 < x_r < w, 0 < y_r < l) — robotun başlanğıc mövqeyinin koordinatları verilir. Robot heç bir butulka ilə eyni nöqtədə yerləşmir.
Robotun bütün butulkaları topladığı ən qısa marşrutun uzunluğunu yazın. Hesablama xətası 10^{-6}-dan çox olmamalıdır.
Nümunə 1