== include(page="template/taskheader" task_id="avioane2") ==
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$.
Poveste şi cerinţă...
h2. Date de intrare
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)$.
Fişierul de intrare $avioane2.in$ ...
h2. Date de ieşire
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$.
În fişierul de ieşire $avioane2.out$ ...
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 |
|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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="avioane2") ==
