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 ai bi, demora ti minutos e diminui a espessura do casco do navio em hi 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 hi 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≤k≤200,2≤n≤2000,1≤m≤10000), separados por espaços.
As próxmias m linhas contém 4 inteiros, ai bi ti hi (1≤ai,bi≤n,1≤ti≤105,0≤hi≤200). A i-ésima linha descreve a i-ésima rota, (que vai da ilha ai, para a ilha bi, leva ti minutos e diminui o casco em hi centímetros). Perceba que ai≠bi.
A ultíma linha de entrada contém dois inteiros A e B (1≤A,B≤N,A≠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 |