politie

Cerință

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.

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 $S_1 \ T_1$ (suma încasată şi durată aplicării unei amenzi de tipul $1$);
• pe linia a treia, două numere naturale $S_2 \ T_2$ (suma încasată şi durată aplicării unei amenzi de tipul $2$);
• pe linia a patra, două numere naturale $S_3 \ T_3$ (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 și precizări

• $0 < T, T_1, T_2, T_3 < 201$
• $0 < S_1, S_2, S_3 < 51$
• $0 < N < 501$
• Evident, există evenimente care intervin simultan în trafic.

Exemplu

politie.in

300
10 20
30 30
50 25
8
1 5
3 10
3 20
1 130
2 142
2 160
3 180
2 280

politie.out

140

Explicație

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