Mrówka pokonująca 1 km w 100 minut chce przejść z punktu początkowego do docelowego na wielkiej równinie. Musi poruszać się równolegle do osi $x$ i $y$, a na terenach pagórkowatych podróż może trwać dłużej. Mając dane oba punkty, tereny pagórkowate i czas przejścia 1 km na każdym z nich, oblicz najkrótszy czas dotarcia mrówki do celu.

Każdy teren pagórkowaty jest prostokątem o bokach równoległych do osi $x$ i $y$, z podanym czasem przejścia 1 km. Czas ten obowiązuje tylko we wnętrzu prostokąta, a nie na jego brzegu. Żadne dwa prostokąty nie nakładają się. Współrzędne $x$ początku, celu i wierzchołków różnych prostokątów są całkowite i nie pokrywają się; to samo dotyczy współrzędnych $y$. Początek i cel zawsze leżą poza prostokątami.

Powyższy rysunek ma współrzędne w kilometrach. Pokazuje prostokąt o lewym dolnym rogu $(0,1)$, prawym górnym $(5,2)$ i czasie 200 minut na kilometr oraz prostokąt o lewym dolnym rogu $(4,3)$, prawym górnym $(9,4)$ i czasie 1000 minut na kilometr. Zaznaczono najszybsze trasy z $A$ do $B$ i z $C$ do $D$; minimalne czasy wynoszą odpowiednio 700 i 1000 minut.

Należy zaimplementować następującą funkcję.

long long shortest_path(pair<int, int> src, pair<int, int> dst,
                        vector<pair<int, int>> p1, vector<pair<int, int>> p2,
                        vector<int> w);

Funkcja zostanie wywołana tylko raz. src i dst to punkt początkowy i docelowy. Lewy dolny róg każdego prostokąta jest podany w p1, a prawy górny w p2. Na podstawie danych zwróć najkrótszy czas przejścia z src do dst.

Szczegóły implementacji

Należy przesłać jeden plik o nazwie plain.cpp, implementujący następującą funkcję.

long long shortest_path(pair<int, int> src, pair<int, int> dst,
                        vector<pair<int, int>> p1, vector<pair<int, int>> p2,
                        vector<int> w);

Funkcja musi działać jak opisano powyżej. Można tworzyć inne funkcje do użytku wewnętrznego. Przesłany kod nie może wykonywać operacji wejścia/wyjścia ani uzyskiwać dostępu do innych plików.

Przykładowy program oceniający

Dostarczony program oceniający czyta wejście w następującym formacie. Współrzędne $x,y$ są w kilometrach.

Pierwszy wiersz: $N\ x_s\ y_s\ x_e\ y_e$.

• $N$: liczba prostokątów.
• $x_s,y_s$: współrzędne $x,y$ początku.
• $x_e,y_e$: współrzędne $x,y$ celu.

Każdy z kolejnych $N$ wierszy: $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$: współrzędne $x,y$ lewego dolnego wierzchołka prostokąta.
• $x_2,y_2$: współrzędne $x,y$ prawego górnego wierzchołka.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$: czas w minutach potrzebny do przejścia 1 km wewnątrz prostokąta.

Dostarczony program oceniający wypisuje wartość zwróconą przez funkcję shortest_path().

Ograniczenia

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$, gdzie $x,y$ to współrzędne początku, celu lub wierzchołka prostokąta.
• $N,w,x,y$ są całkowite.

Podzadania

1. (23 punktów) $N\le500$
2. (35 punktów) $N\le5000$
3. (31 punktów) $x_2-x_1=1$
4. (61 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3 2 14 5 1
4 6 6 10 1000
0 7 3 9 200
1 2 8 5 150

Wyjście 1

1750

Wejście 2

13 0 38 100 25
1 39 2 46 190
9 78 10 80 230
20 42 21 89 170
27 26 28 68 170
35 41 36 99 270
43 36 44 63 280
51 15 52 27 150
57 14 58 29 190
64 2 65 90 160
75 33 76 35 290
78 5 79 100 290
88 28 89 40 190
94 7 95 50 250

Wyjście 2

11770