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