Processing math: 100%

Avançado Informática - Semana 41

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 (1k200,2n2000,1m10000), separados por espaços.

As próxmias m linhas contém 4 inteiros, ai bi ti hi (1ai,bin,1ti105,0hi200). 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 aibi.

A ultíma linha de entrada contém dois inteiros A e B (1A,BN,AB), 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