Gigel şi Costel sunt doi poliţişti cu experienţă. Ei lucrează împreună de mulţi ani şi de multe ori au fost nominalizaţi pentru premiul „Poliţiştii anului”. Anul acesta sunt hotărâţi să-l câştige şi pentru aceasta trebuie să încaseze cât mai mulţi bani din amenzi.
În fiecare zi, Gigel şi Costel pot aplica trei tipuri de amenzi pentru următoarele evenimente:
Amenzile de tipul 1 şi 2 pot fi aplicate de un singur poliţist (Gigel sau Costel). Pentru o amendă de tipul 3, Gigel şi Costel trebuie să lucreze împreună (unul verifică actele de transport, iar celălalt verifică marfa).
Durata de aplicare a unei amenzi reprezintă timpul necesar poliţiştilor pentru a verifica acte, a scrie proces verbal, etc. Dacă un poliţist aplică o amendă la momentul x, iar durata aplicării amenzii este y, poliţistul care aplică amenda va deveni disponibil abia la momentul x+y. Poliţiştii nu fac minute suplimentare, ei sunt în activitate din minutul 1 până în minutul T exclusiv, deci trebuie să fie liberi să plece acasă în minutul T. Pentru că în noul cod rutier nu le mai este permis poliţiştilor să tragă şoferii pe dreapta şi să-i lase să aştepte, pentru a aplica o amendă de tipul 1 sau 2 trebuie să fie liber măcar un poliţist, iar pentru a aplica o amendă de tipul 3 ambii poliţişti trebuie să fie liberi la momentul în care survine evenimentul.
Cei doi poliţişti stau la pândă şi observă evenimentele din trafic. Dacă nu pot aplica amenzi pentru toate evenimentele care intervin în trafic, ei sunt nevoiţi să le aleagă pe acelea care, în total, le aduc mai mulţi bani.
Cerinţă
Scrieţi un program care să determine suma maximă pe care o pot încasa din amenzi Gigel şi Costel într-o tură.
Date de intrare
Fişierul de intrare politie.in conţine:
– pe prima linie numărul natural T, reprezentând minutul la care cei doi poliţişti sunt liberi să plece acasă;
– pe linia a doua, două numere naturale S1 T1 (suma încasată şi durată aplicării unei amenzi de tipul 1);
– pe linia a treia, două numere naturale S2 T2 (suma încasată şi durată aplicării unei amenzi de tipul 2);
– pe linia a patra, două numere naturale S3 T3 (suma încasată şi durată aplicării unei amenzi de tipul 3);
– pe linia a cincea, un număr natural N (numărul de evenimente survenite în trafic);
– pe fiecare dintre următoarele N linii se află două numere naturale tip timp (tip poate fi 1, 2 sau 3 şi reprezentă tipul amenzii ce poate fi aplicată; timp reprezintă timpul la care a survenit evenimentul, exprimat în număr de minute faţă de începutul turei).
Numerele scrise pe aceeaşi linie sunt separate prin câte un spaţiu. Evenimentele sunt în ordine cronologică.
Date de ieşire
Fişierul de ieşire politie.out conţine o singură linie pe care este scrisă suma maximă ce poate fi încasată.
Restricţii
0 < T, T1, T2, T3 <201
0 < S1, S2, S3 < 51
0 < N < 501
Evident, există evenimente care intervin simultan în trafic.
Aplică amândoi amenda de tipul 3 din minutul 10, apoi Costel aplică singur amenda de tipul 1 din minutul 130, apoi Gigel aplică singur amenda de tipul 2 din minutul 142, apoi amândoi aplică amenda de tipul 3 din minutul 180.
