trenuri

Trenuri

== include(page="template/taskheader" task_id="trenuri") ==

Poveste şi cerinţă...

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.
 
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 bun mod de a ajunge din oraşul $1$ în oraşul $N$, conform cerinţelor lui Ivan.

h2. Date de intrare

Fişierul de intrare $trenuri.in$ ...

Pe prima linie a fişierului $trenuri.in$ se află $3$ numere întregi: $N$ (numărul de oraşe), $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 în $b$ la momentul de timp $s$, şi costul unui bilet la acest tren este $c$.

h2. Date de ieşire

În fişierul de ieşire $trenuri.out$ ...

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

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 15 000$
* $2 ≤ M ≤ 200 000$
* $0 ≤ c ≤ 10 000$
* $0 ≤ B ≤ 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 &le; p$. Timpul de aşteptare este $p – s$.
* 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
table(example). |_. trenuri.in |_. trenuri.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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
| 4 19

|
h3. Explicaţie

...

Ivan ia î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$.

== include(page="template/taskfooter" task_id="trenuri") ==

4010