Mətbəx robotu

Robotlar zamanla daha da populyarlaşır. Bu gün onları yalnız böyük zavodlarda deyil, həm də ev şəraitində istifadə edirlər. Bir proqramçı dostları ilə birlikdə öz ev robotunu yaratmağa qərar verdi. Bildiyiniz kimi, əksər proqramçılar axşamlar toplaşıb pivə içməyi sevirlər. Bu tədbirdən sonra masada çoxlu boş şüşələr qalır. Buna görə də masadan boş şüşələri toplaya bilən bir robot yaratmağa qərar verildi.

Masa uzunluğu $l$ və eni $w$ olan bir düzbucaqlıdır. Robot $(x_r,y_r)$ nöqtəsindən başlayır və $n$ şüşə $(x_i,y_i)(1\le i\le n)$ nöqtələrində yerləşir. Şüşəni götürmək üçün robot onun yerləşdiyi nöqtəyə hərəkət etməli və onu götürməlidir, sonra isə şüşəni masanın sərhədindəki bir nöqtəyə aparıb buraxmalıdır. Robot istənilən anda yalnız bir şüşə tuta bilər və onu yalnız masanın sərhədində buraxa bilər.

Şüşələrin və robotun ölçülərini o qədər kiçik hesab edin ki, onlara məhəl qoyulmasın (robot və şüşələr nöqtələrdir). Robot, şüşəni tutarkən, başqa bir şüşənin yerləşdiyi nöqtədən keçə bilər.

Robotun alt proqramlarından biri marşrut planlaşdırmasıdır. Sizdən robotun bütün şüşələri toplayacağı minimal uzunluqlu marşrutu tapacaq bir proqram yazmağınız tələb olunur.

Giriş verilənləri

Birinci sətir masanın eni və uzunluğu olan iki tam ədəd $w$ və $l(2\le w,l\le 1000)$ ehtiva edir.

İkinci sətir masadakı şüşələrin sayını $n(1\le n\le 18)$ ehtiva edir. Növbəti $n$ sətirin hər biri $i$-ci şüşənin koordinatları olan iki tam ədəd $x_i$ və $y_i(0<x_i<w,0<y_i<l)$ ehtiva edir. Heç bir iki şüşə eyni nöqtədə yerləşmir.

Giriş məlumatlarının son sətiri robotun başlanğıc mövqeyinin koordinatları olan iki tam ədəd $x_r$ və $y_r(0<x_r<w,0<y_r<l)$ ehtiva edir. Robot heç bir şüşə ilə eyni nöqtədə yerləşmir.

Çıxış verilənləri

Robotun bütün şüşələri toplayacağı ən qısa yolun uzunluğunu çıxarın. Hesablama dəqiqliyi $10^{-6}$-dan çox olmamalıdır.

Nümunələr