Convex Hull

Matheus está viajando com o seu navio em um arquipélago. Seu navio tem um casco convexo que tem $k$ centímetros de espessura. O aruipélago tem $n$ ilhas, numeradas de $1$ a $n$. Existem $m$ rotas marítmas entre as ilhas, onde a $i$-ésima rota liga duas diferentes ilhas $a_i\ b_i$, demora $t_i$ minutos e diminui a espessura do casco do navio em $h_i$ centímetros. Podem haver varias rotas entre o mesmo par de ilhas.

Matheus quer viajar entre as ilhas $A$ e $B$, por meio de uma sequência de rotas marítmas, de forma que o casco do seu navio continue intacto. Em outras palavras, de tal forma que a soma do $h_i$ das rotas seja entritamente menor que $k$.

Além disso Matheus está apressado, e quer minímizar o tempo necessário para chegar na ilha $B$ saindo da ilha $A$. Pode não ser possível chegar na ilha $B$ partindo da ilha, seja por não haver rotas suficientes ou por o casco do navio ser destruído.

Entrada

A primeira linha contém 3 inteiros $k, n, m\ (1 \leq k \leq 200, 2 \leq n \leq 2000, 1 \leq m \leq 10000)$, separados por espaços.

As próxmias $m$ linhas contém 4 inteiros, $a_i\ b_i\ t_i\ h_i\ (1 \leq a_i,b_i \leq n, 1 \leq t_i \leq 10^5, 0 \leq h_i \leq 200)$. A $i$-ésima linha descreve a $i$-ésima rota, (que vai da ilha $a_i$, para a ilha $b_i$, leva $t_i$ minutos e diminui o casco em $h_i$ centímetros). Perceba que $a_i \neq b_i$.

A ultíma linha de entrada contém dois inteiros $A$ e $B\ (1 \leq A,B \leq N, A \neq B)$, as ilhas por onde queremos ir.

Saída

Imprima um inteiro, representando o tempo mínimo para viajar de $A$ para $B$ sem destruir o casco do navio, ou -1 caso isso seja impossível.

Exemplos

Entrada	Saída
10 4 7 1 2 4 4 1 3 7 2 3 1 8 1 3 2 2 2 4 2 1 6 3 4 1 1 1 4 6 12 1 4	7
3 3 3 1 2 5 1 3 2 8 2 1 3 1 3 1 3	-1