== include(page="template/taskheader" task_id="avioane2") ==
Poveste şi cerinţă...
Mihai si Alexandra s-au decis sa mearga in vacanta in strainatate. Problema lui Mihai este ca mereu Alexandra trebuie sa decida daca are rost sa mearga intr-o anumita excursie sau nu (in functie de bani, timp, etc.).
Fie $N$ aeroporturi (reprezentate ca nodurile unui graf) si $M$ zboruri (muchiile grafului). Pentru fiecare zbor se cunoaste indicele aeroportului si timpul la care decoleaza avionul, indicele aeroportului si timpul la care aterizeaza avionul si pretul biletului pentru acest zbor. Mihai si Alexandra se afla in aeroportul $1$ la timpul $0$. Mihai trebuie sa raspunda la $K$ query-uri de tipul $(x,y):$ care este pretul minim pentru a ajunge in aeroportul $x$ la timpul maxim $y$.
h2. Date de intrare
Fişierul de intrare $avioane2.in$ ...
Fişierul de intrare $avioane2.in$ va contine pe prima linie $3$ numere naturale $N$, $M$ si $K$. Pe urmatoarele $M$ linii se afla cate $5$ valori reprezentand detaliile unui zbor: $A$, $T{~dec~}$, $B$, $T{~Ater~}$ (avionul pleaca din $A$ la timpul $T{~dec~}$ si ajunge in B la timpul $T{~Ater~}$) si $P$, pretul biletului. Urmatoarele $K$ linii contin cate $2$ numere naturale reprezentand query-urile de tipul $(x,y)$.
h2. Date de ieşire
În fişierul de ieşire $avioane2.out$ ...
Fişierul de ieşire $avione.out$ va contine $K$ linii, rasunsul pentru fiecare query. Daca nu se poate ajunge intr-un anumit pana la un anumit timp dat, afisati $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 30.000$
* $1 ≤ M ≤ 90.000$
* $1 ≤ K ≤ 120.000$
* Toate celalalte valori fac parte din intervalul $[1, 10^9^]$
* Mihai si Alexandra trebuie sa plateasca un singur bilet pentru fiecare zbor.
* Personajele pot astepta oricat intr-un aeroport (la o cafea) urmatorul zbor.
* $T{~dec~} < T{~Ater~}$ pentru fiecare din cele $M$ zboruri
h2. Exemplu
table(example). |_. avioane2.in |_. avioane2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 7 6
1 4 5 8 69
2 14 3 17 25
4 2 5 10 564
5 8 2 13 12
3 20 1 25 54
2 4 4 7 34
1 1 3 8 1000
3 10
3 20
5 7
2 20
1 100
5 13
|1000
106
-1
81
0
69
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="avioane2") ==
