Última conexão

Time limit: 3000 msMemory limit: 256 MB

Há $N$ estações e $M$ serviços de transporte dirigidos. Um serviço de $u$ para $v$ tem duração $d$ e partidas nos instantes

a,\ a+p,\ a+2p,\ \ldots,\ a+kp \le b.

Aqui, $k$ percorre os inteiros não negativos; $b$ é apenas um limite e não precisa ser um instante de partida. Você começa na estação $S$ no instante $T$ . Pode esperar em qualquer estação por quanto tempo quiser e embarcar em uma partida no exato instante de sua chegada. Não há tempo adicional de transferência.

Determine o menor instante em que é possível chegar à estação $F$ , ou informe que isso é impossível. Serviços entre o mesmo par de estações e serviços de uma estação para ela mesma são permitidos.

Input

A primeira linha contém $N$ , $M$ , $S$ , $F$ e $T$ . Cada uma das próximas $M$ linhas contém , , , , e , descrevendo um serviço.

Output

Imprima o menor instante de chegada, ou -1 se não houver viagem possível. Se $S=F$ , a resposta é $T$ .

Samples

Sample 1

Input

3 4 1 3 1
1 2 4 0 5 10
2 3 3 3 5 13
1 3 20 0 1 20
1 2 2 6 1 6

Output

É possível partir às 6 pelo quarto serviço, chegar à estação 2 às 8 e embarcar imediatamente no segundo serviço, chegando às 11.

Sample 2

Input

2 1 1 2 9
1 2 2 0 4 9

Output

-1

As partidas são às 0, 4 e 8. O limite 9 não cria uma partida às 9.