Une fourmi qui parcourt 1 km en 100 minutes veut aller d’un point de départ à une destination sur une grande plaine. Elle doit se déplacer parallèlement aux axes $x$ et $y$, et le trajet peut prendre plus de temps dans les zones vallonnées. Étant donnés le départ, la destination, les zones vallonnées et le temps nécessaire pour parcourir 1 km dans chacune, calculez le temps minimal pour atteindre la destination.

Chaque zone vallonnée est un rectangle aux côtés parallèles aux axes $x$ et $y$, avec un temps de trajet par kilomètre donné. Ce temps s’applique seulement à l’intérieur du rectangle, pas à son bord. Deux rectangles ne se chevauchent jamais. Les coordonnées $x$ du départ, de la destination et des sommets de rectangles différents sont entières et ne coïncident pas ; il en va de même pour les coordonnées $y$. Le départ et la destination sont toujours à l’extérieur des rectangles.

La figure ci-dessus utilise des coordonnées en kilomètres. Elle montre un rectangle de coin inférieur gauche $(0,1)$, de coin supérieur droit $(5,2)$ et de temps de trajet de 200 minutes par kilomètre, et un autre de coin inférieur gauche $(4,3)$, de coin supérieur droit $(9,4)$ et de 1000 minutes par kilomètre. Les trajets les plus rapides de $A$ à $B$ et de $C$ à $D$ sont indiqués ; leurs temps minimaux sont respectivement de 700 et 1000 minutes.

Vous devez implémenter la fonction suivante.

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

Cette fonction n’est appelée qu’une fois. src et dst sont le départ et la destination. Le coin inférieur gauche de chaque rectangle est donné dans p1, et le coin supérieur droit dans p2. À partir des valeurs données, renvoyez le temps minimal de trajet de src à dst.

Détails d'implémentation

Vous devez soumettre un fichier nommé plain.cpp, qui implémente la fonction suivante.

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

La fonction doit se comporter comme décrit ci-dessus. Vous pouvez créer d’autres fonctions à usage interne. Le code soumis ne doit pas effectuer d’entrées/sorties ni accéder à d’autres fichiers.

Programme d’évaluation d’exemple

Le programme d’évaluation fourni lit l’entrée au format suivant. Les coordonnées $x,y$ sont en kilomètres.

Première ligne : $N\ x_s\ y_s\ x_e\ y_e$.

• $N$ : nombre de rectangles.
• $x_s,y_s$ : coordonnées $x,y$ du départ.
• $x_e,y_e$ : coordonnées $x,y$ de la destination.

Chacune des $N$ lignes suivantes : $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$ : coordonnées $x,y$ du coin inférieur gauche du rectangle.
• $x_2,y_2$ : coordonnées $x,y$ du coin supérieur droit.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$ : temps en minutes pour parcourir 1 km à l’intérieur du rectangle.

Le programme d’évaluation fourni affiche la valeur renvoyée par votre fonction shortest_path().

Contraintes

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$, où $x,y$ sont des coordonnées du départ, de la destination ou d’un sommet de rectangle.
• $N,w,x,y$ sont tous entiers.

Sous-tâches

1. (23 points) $N\le500$
2. (35 points) $N\le5000$
3. (31 points) $x_2-x_1=1$
4. (61 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

1750

Entrée 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

Sortie 2

11770