Una hormiga que recorre 1 km en 100 minutos quiere ir desde un punto inicial hasta un destino en una gran llanura. Debe moverse paralelamente a los ejes $x$ e $y$, y puede tardar más en las zonas de colinas. Dados el inicio, el destino, las zonas de colinas y el tiempo para recorrer 1 km en cada una, calcula el tiempo mínimo para llegar al destino.

Cada zona de colinas es un rectángulo con lados paralelos a los ejes $x$ e $y$, con un tiempo de viaje por kilómetro especificado. Este tiempo solo se aplica en su interior, no en su borde. Ningún par de rectángulos se solapa. Las coordenadas $x$ del inicio, el destino y los vértices de rectángulos distintos son enteras y no coinciden; lo mismo se cumple para sus coordenadas $y$. El inicio y el destino siempre están fuera de los rectángulos.

La figura anterior usa coordenadas en kilómetros. Muestra un rectángulo de esquina inferior izquierda $(0,1)$ y superior derecha $(5,2)$, con 200 minutos por kilómetro, y otro de esquina inferior izquierda $(4,3)$ y superior derecha $(9,4)$, con 1000 minutos por kilómetro. Se muestran las rutas más rápidas de $A$ a $B$ y de $C$ a $D$; sus tiempos mínimos son 700 y 1000 minutos, respectivamente.

Debes implementar la siguiente función.

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 función se llama una sola vez. src y dst son el inicio y el destino. La esquina inferior izquierda de cada rectángulo se da en p1, y la superior derecha en p2. Con los valores dados, devuelve el tiempo mínimo de viaje de src a dst.

Detalles de implementación

Debes enviar un archivo llamado plain.cpp que implemente la siguiente función.

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 función debe comportarse como se ha descrito. Puedes crear otras funciones para uso interno. El código enviado no debe realizar entrada/salida ni acceder a otros archivos.

Evaluador de ejemplo

El evaluador proporcionado lee la entrada en el siguiente formato. Las coordenadas $x,y$ están en kilómetros.

Primera línea: $N\ x_s\ y_s\ x_e\ y_e$.

• $N$: número de rectángulos.
• $x_s,y_s$: coordenadas $x,y$ del inicio.
• $x_e,y_e$: coordenadas $x,y$ del destino.

Cada una de las siguientes $N$ líneas: $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$: coordenadas $x,y$ de la esquina inferior izquierda del rectángulo.
• $x_2,y_2$: coordenadas $x,y$ de su esquina superior derecha.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$: tiempo en minutos para recorrer 1 km dentro del rectángulo.

El evaluador proporcionado imprime el valor devuelto por tu función shortest_path().

Restricciones

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$, donde $x,y$ son coordenadas del inicio, el destino o un vértice de rectángulo.
• $N,w,x,y$ son enteros.

Subtareas

1. (23 puntos) $N\le500$
2. (35 puntos) $N\le5000$
3. (31 puntos) $x_2-x_1=1$
4. (61 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

1750

Entrada 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

Salida 2

11770