Uma formiga que percorre 1 km em 100 minutos quer ir de um ponto inicial a um destino em uma grande planície. Ela deve se mover paralelamente aos eixos $x$ e $y$, e a viagem pode demorar mais nas áreas de colinas. Dados o início, o destino, as áreas de colinas e o tempo para percorrer 1 km em cada uma, calcule o tempo mínimo para a formiga chegar ao destino.

Cada área de colinas é um retângulo com lados paralelos aos eixos $x$ e $y$, com um tempo de viagem por quilômetro especificado. Esse tempo se aplica apenas ao interior do retângulo, não à borda. Dois retângulos nunca se sobrepõem. As coordenadas $x$ do início, do destino e dos vértices de retângulos distintos são inteiras e não coincidem; o mesmo vale para as coordenadas $y$. O início e o destino estão sempre fora dos retângulos.

A figura acima usa coordenadas em quilômetros. Ela mostra um retângulo de canto inferior esquerdo $(0,1)$ e superior direito $(5,2)$, com 200 minutos por quilômetro, e outro de canto inferior esquerdo $(4,3)$ e superior direito $(9,4)$, com 1000 minutos por quilômetro. As rotas mais rápidas de $A$ a $B$ e de $C$ a $D$ estão indicadas; os tempos mínimos são, respectivamente, 700 e 1000 minutos.

Você deve implementar a função a seguir.

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

A função é chamada apenas uma vez. src e dst são o início e o destino. O canto inferior esquerdo de cada retângulo é dado em p1, e o superior direito em p2. Com os valores dados, retorne o tempo mínimo de viagem de src a dst.

Detalhes de implementação

Você deve enviar um arquivo chamado plain.cpp, implementando a função a seguir.

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

A função deve se comportar como descrito acima. Você pode criar outras funções para uso interno. O código enviado não deve realizar entrada/saída nem acessar outros arquivos.

Avaliador de exemplo

O avaliador fornecido lê a entrada no formato a seguir. As coordenadas $x,y$ estão em quilômetros.

Primeira linha: $N\ x_s\ y_s\ x_e\ y_e$.

• $N$: número de retângulos.
• $x_s,y_s$: coordenadas $x,y$ do início.
• $x_e,y_e$: coordenadas $x,y$ do destino.

Cada uma das próximas $N$ linhas: $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$: coordenadas $x,y$ do canto inferior esquerdo do retângulo.
• $x_2,y_2$: coordenadas $x,y$ do canto superior direito.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$: tempo em minutos para percorrer 1 km dentro do retângulo.

O avaliador fornecido imprime o valor retornado pela sua função shortest_path().

Restrições

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$, em que $x,y$ são coordenadas do início, do destino ou de um vértice de retângulo.
• $N,w,x,y$ são inteiros.

Subtarefas

1. (23 pontos) $N\le500$
2. (35 pontos) $N\le5000$
3. (31 pontos) $x_2-x_1=1$
4. (61 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

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

Saída 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

Saída 2

11770