Eine Ameise, die für 1 km 100 Minuten benötigt, möchte auf einer großen Ebene vom Start zum Ziel gelangen. Sie muss sich parallel zu den $x$- und $y$-Achsen bewegen; in hügeligen Gebieten kann die Reise länger dauern. Berechne anhand von Start, Ziel, Hügelgebieten und der dort jeweils für 1 km benötigten Zeit die minimale Reisezeit der Ameise.

Jedes Hügelgebiet ist ein Rechteck mit zu den $x$- und $y$-Achsen parallelen Seiten und einer vorgegebenen Reisezeit pro Kilometer. Diese gilt nur im Inneren des Rechtecks, nicht auf seinem Rand. Keine zwei Rechtecke überlappen sich. Die $x$-Koordinaten von Start, Ziel und Eckpunkten unterschiedlicher Rechtecke sind ganzzahlig und fallen nicht zusammen; dasselbe gilt für die $y$-Koordinaten. Start und Ziel liegen stets außerhalb der Rechtecke.

Die Abbildung oben verwendet Kilometerkoordinaten. Sie zeigt ein Rechteck mit linker unterer Ecke $(0,1)$, rechter oberer Ecke $(5,2)$ und 200 Minuten pro Kilometer sowie eines mit linker unterer Ecke $(4,3)$, rechter oberer Ecke $(9,4)$ und 1000 Minuten pro Kilometer. Die schnellsten Wege von $A$ nach $B$ und von $C$ nach $D$ sind eingezeichnet; die minimalen Zeiten betragen 700 beziehungsweise 1000 Minuten.

Du musst die folgende Funktion implementieren.

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);

Die Funktion wird nur einmal aufgerufen. src und dst sind Start und Ziel. Die linke untere Ecke jedes Rechtecks steht in p1, die rechte obere in p2. Ermittle anhand der gegebenen Werte die minimale Reisezeit von src nach dst und gib sie zurück.

Implementierungsdetails

Du musst eine Datei namens plain.cpp einreichen, die die folgende Funktion implementiert.

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);

Die Funktion muss sich wie oben beschrieben verhalten. Weitere Funktionen für den internen Gebrauch sind erlaubt. Der eingereichte Code darf keine Ein-/Ausgabe durchführen und nicht auf andere Dateien zugreifen.

Beispiel-Bewertungsprogramm

Das bereitgestellte Bewertungsprogramm liest die Eingabe im folgenden Format. Die $x,y$-Koordinaten sind in Kilometern angegeben.

Erste Zeile: $N\ x_s\ y_s\ x_e\ y_e$.

• $N$: Anzahl der Rechtecke.
• $x_s,y_s$: $x,y$-Koordinaten des Starts.
• $x_e,y_e$: $x,y$-Koordinaten des Ziels.

Jede der nächsten $N$ Zeilen: $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$: $x,y$-Koordinaten der linken unteren Rechteckecke.
• $x_2,y_2$: $x,y$-Koordinaten der rechten oberen Ecke.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$: Zeit in Minuten für 1 km innerhalb des Rechtecks.

Das bereitgestellte Bewertungsprogramm gibt den Rückgabewert deiner Funktion shortest_path() aus.

Beschränkungen

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$, wobei $x,y$ Koordinaten von Start, Ziel oder einer Rechteckecke sind.
• $N,w,x,y$ sind alle ganzzahlig.

Teilaufgaben

1. (23 Punkte) $N\le500$
2. (35 Punkte) $N\le5000$
3. (31 Punkte) $x_2-x_1=1$
4. (61 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

1750

Eingabe 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

Ausgabe 2

11770