trenuri

Ivan trebuie să ajungă la Cluj-Napoca pentru a participa la pregatirile Lotului National de Informatică. Pentru aceasta, el a ales ca mijloc de transport trenul. El dispune de la Ministerul Educatiei, Cercetării şi Inovării de o sumă pentru transport pe care nu trebuie să o depaşească. Lui Ivan nu-i place să aştepte, aşa că ar dori ca timpul maxim de aşteptare între două trenuri să fie cât mai mic.

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$.

Date de intrare

Pe prima linie a fişierului trenuri.in se află $3$ numere întregi, $N$ (numărul de orase), $M$ (numărul de trenuri) şi $B$ (bugetul lui Ivan). Pe următoarele $M$ linii se găsesc descrierile trenurilor. Pe linia $i + 1$ se găsesc numerele întregi $a, b, c, p, s$ (separate prin câte un singur spaţiu) cu semnificaţia că există un tren care pleacă din oraşul $a$ la momentul de timp $p$, ajunge la $b$ în momentul de timp $s$, şi costul unui bilet la acest tren este $c$.

Date de ieșire

În fişierul trenuri.out se vor scrie pe prima linie $2$ numere întregi, $T$ şi $C$, reprezentând timpul minim de aşteptare şi costul biletelor. În cazul mai multor soluţii cu acelaşi $T$ se va afişa soluţia cu $C$ minim.

Restricții și precizări

• $2 \leq N \leq 15 \ 000$
• $2 \leq M \leq 200 \ 000$
• $0 \leq c \leq 10 \ 000$
• $0 \leq B \leq 2 \ 000 \ 000 \ 000$
• 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 \leq 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

Exemplul 1

trenuri.in

5 6 20
1 2 4 2 8
2 4 5 9 11
1 3 5 1 5
3 4 1 2 6
4 5 13 12 14
4 5 10 15 20

trenuri.out

4 19

Explicație

Ivan ia mai întâi trenul din oraşul $1$ spre oraşul $2$. Din oraşul $2$ ia trenul spre oraşul $4$, aşteptând o unitate de timp. Dupa aceea ia trenul spre oraşul $5$ la timpul $15$, asteptând $4$ unităţi de timp. Timpul maxim de aşteptare este $4$ unităţi de timp, iar costul total este $19$.