h2. Cerinţă

Fiind date bugetul lui Ivan şi lista tuturor trenurilor care circulă, împreună cu costul unui bilet, ora de plecare şi ora de sosire a trenului, să se găsească cel mai ieftin mod de a ajunge din oraşul $1$ în oraşul $N$.

Fiind date bugetul lui Ivan şi lista tuturor trenurilor care circulă, împreună cu costul unui bilet, ora de plecare şi ora de sosire a trenului, să se găsească cel mai bun mod de a ajunge din oraşul $1$ în oraşul $N$, conform cerinţelor lui Ivan.

h2. Date de intrare

* Pentru oricare tren $p < s$.
* Timpul de aşteptare nu se contorizează în staţia de început. Ivan poate veni de acasă la orice oră doreşte.
* Un tren care pleacă la momentul $p$ poate fi luat doar dacă Ivan ajunge în staţia de plecare la un moment de timp $s &le; p$. Timpul de aşteptare este $p – s$.

* Există soluţie pentru toate testele.
* Ivan vă recomandă să parsaţi fişierul de intrare. Astfel, veţi avea mai mult timp ca să-l ajutaţi.

* Există soluţie pentru toate testele, iar timpul maxim de asteptare este cel mult $200 000$ unităţi.
* Ivan vă recomandă să parsaţi fişierul de intrare. Astfel, veţi avea mai mult timp să-l ajutaţi.

h2. Exemplu

4010