amenzi

Amenzi

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

Ion este politist intr-un mare oras. In oras exista $N$ intersectii legate intre ele prin intermediul a $M$ strazi pe care se poate circula in ambele sensuri. Pentru fiecare strada se stie timpul $C{~i~}$ necesar pentru a o parcurge. Informat de o sursa sigura Ion stie ca in cursul urmatoarei zile se vor petrece $K$ infractiuni. Pentru fiecare infractiune $i$ se cunosc urmatoarele date: $T{~i~}$ - timpul la care infractiunea are loc, $A{~i~}$ - intersectia in care infractiunea are loc, $S{~i~}$ - amenda pe care Ion o poate da daca se afla in intersectia $S{~i~}$ la momentul $T{~i~}$.

Ion este politist intr-un mare oras. In oras exista $N$ intersectii legate intre ele prin intermediul a $M$ strazi pe care se poate circula in ambele sensuri. Pentru fiecare strada se stie timpul $C{~i~}$ necesar pentru a o parcurge. Informat de o sursa sigura Ion stie ca in cursul urmatoarei zile se vor petrece $K$ infractiuni. Pentru fiecare infractiune $i$ se cunosc urmatoarele date: $T{~i~}$ - timpul la care infractiunea are loc, $A{~i~}$ - intersectia in care infractiunea are loc, $S{~i~}$ - amenda pe care Ion o poate da daca se afla in intersectia $A{~i~}$ la momentul $T{~i~}$.

Stie ca in cursul zilei urmatoare trebuie sa se intalneasca cu sotia sa, dar nu mai stie exact nici timpul nici ora la care trebuie sa faca acest lucru. Tot ce isi aminteste sunt $P$ perechi de forma $X{~i~}$, $Y{~i~}$ care semnifica faptul ca s-ar putea sa trebuiasca sa se intalneasca cu sotia sa la momentul $Y{~i~}$ in intersectia {$X{~i~}$}.

Stie ca in cursul zilei urmatoare trebuie sa se intalneasca cu sotia sa, dar nu mai stie exact nici locul nici ora la care trebuie sa faca acest lucru. Tot ce isi aminteste sunt $P$ perechi de forma $X{~i~}$, $Y{~i~}$ care semnifica faptul ca s-ar putea sa trebuiasca sa se intalneasca cu sotia sa la momentul $Y{~i~}$ in intersectia {$X{~i~}$}.

Avand la dispozitie toate aceste date ajutati-l pe Ion sa afle valoare maxima totala a amenzilor pe care o poate da pentru fiecare din cele $P$ perechi pe care si le aminteste. Din momentul in care se intalneste cu sotia sa Ion nu va mai da amenzi.

h2. Date de iesire

In fisierul de iesire $amenzi.out$ vor exista $P$ linii coninand valoarea totala maxima pe care Ion o va obtine din amenzi in fiecare din cele $P$ cazuri descrise in fisierul de intrare.

In fisierul de iesire $amenzi.out$ vor exista $P$ linii continand valoarea totala maxima pe care Ion o va obtine din amenzi in fiecare din cele $P$ cazuri descrise in fisierul de intrare. Daca Ion nu poate ajunge sub nici o forma in intersectia respectiva la momenul stabilit afisati $-1$ pe testul respectiv.

h2. Restrictii
* Initial Ion se afla in intersectia $1$ la momentul {$0$}.

* Timpii la care se petrec infractiunile si la care Ion se poate intalni cu sotia sa sunt in intervalul [{$0, 1000$}]
* 0 ≤ K ≤ 1000
* 1 ≤ N ≤ 100
* 1 ≤ M ≤ 1000
* Costul unei amenzi va fi un intreg din intervalul [{$1, 1000$}]

* Timpii la care se petrec infractiunile si la care Ion se poate intalni cu sotia sa sunt in intervalul [{$0, 3500$}]
* {$0 ≤ K ≤ 12000$}
* {$0 ≤ P ≤ 8000$}
* {$1 ≤ N ≤ 150$}
* {$1 ≤ M ≤ 1500$}
* Timpul necesar parcurgerii unei strazi este un numar intreg strict pozitiv
* Costul unei amenzi va fi un intreg din intervalul [{$1, 10000$}]

h2. Exemplu
table(example). |_. amenzi.in |_. amenzi.out |

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

| 5 7 4 2
5 4 4
4 3 5
2 3 7
3 1 3
5 2 3
4 1 10
4 2 1
2 6 5736
2 20 2567
5 6 1530
3 3 4067
1 50
3 15
| 6634
4067

|
h3. Explicatie

...

Pentru primul caz Ion va merge in intersectia 3 unde va ajunge la momentul 3 exact la timp pentru a da o amenda in valoare de 4067. Apoi merge in intersectia 2 unde ajunge la momentul 10. Aici asteapta pana la momentul 20 cand da amenda in valoare de 2567. El merge apoi la intersectia 1 unde isi va astepta sotia pana la momentul 50.
 
Pentru al doilea caz Ion merge in intersectia 3 unde ajunge la momentul 3, da amenda in valoare de 4067 apoi isi asteapta sotia pana la momentul 15.

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

1494