Ropociąg (AiSD14)
Szejk Abdul-Bit-Constant posiada wiele pól naftowych. Teraz planuje rozszerzyć działalność także o rafinowanie ropy. W tym celu wybudował rafinerię. Musi jeszcze połączyć ją ropociągiem ze wszystkimi polami naftowymi. Do zaprojektowania ropociągu zatrudnił Ciebie. Twoim wynagrodzeniem będzie stado wielbłądów, pomniejszone o jednego wielbłąda za każdy zbudowany kilometr ropociągu. Zainteresowany jesteś więc minimalizacją łącznej długości położonych rur. Z powodów geologicznych ropociąg musi mieć postać rury głównej, biegnącej z zachodu na wzchód orazi rur łączących pola naftowe i rafinerię z rurociągiem głównym. Rury łączące muszą biec wzdłuż południków: z północy na południe bądź z południa na północ.
Uwaga: Implementacja szukania mediany w czasie liniowym daje 10 punktów. Implementacja algorytmu shellsort o złożoności O(nlog2n) daje 5 punktów. Skorzystnie z innych algorytmów nie daje punktów.



Wejście
Program powinien wczytać z klawiatury kolejno:
n - liczbę pól naftowych (nie więszą niż 1000000),
x y - współrzędne rafinerii,
x1 y1 - współrzędne pierwszego pola naftowego,
...
xn yn - współrzędne ostatniego pola naftowego.
Jednostkami współrzędnych są kilometry. Żadne dwa pola naftowe nie będą miały takiej samej wartości współrzędnej x. Rafineria nie będzie miała takiej samej wartości współrzędnej x jak którekolwiek pole naftowe.

Wyjście
Program powinien wypisać na ekran łączną długość rur (w kilometrach), które należy położyć, aby połączyć pola naftowe z rafinerią.

Przykład (z rysunku)
Wejście:
3
8 7
4 8
2 1
5 4

Wyjście:
16

Wejście:
4
8 5
7 0
1 4
9 1
9 3

Wyjście:
16