Ajutaţi conducerea să afle timpul minim în care toate persoanele şi grupurile din ambele cozi se dau cu tractorul.

h2. Date de intrare
Fişierul de intrare $tractor.in$ conţine pe prima linie numerele întregi $N$, $M$ şi $P$, cu semnificaţia: $N$ - numărul de persoane ce intră în prima coadă; $M$ - numărul de grupuri ce intră în a doua coadă; $P$ - durata unei curse cu tractorul.
Pe următoarele $N+M$ linii, se află câte trei numere întregi $t$ $d$ $c$. Dacă $d$ este $1$, atunci este vorba de o persoană care la momentul $t$ se aşază în prima coadă şi are durata de îmbarcare $c$. Dacă $d$ este $2$, $3$ sau $4$, atunci este vorba de un grup de $d$ persoane care la momentul $t$ se aşază în a doua coadă şi are durata de îmbarcare $c$. Timpii daţi în fişierul de intrare sunt în ordine crescătoare.

h2. Date de ieşire
Fişierul de ieşire $tractor.out$ trebuie să conţină un singur număr întreg $T$ care reprezintă timpul minim în care toate persoanele din prima coadă şi grupurile din a doua coadă se dau cu tractorul.

h2. Restricţii
* $0 ≤ N ≤ 3 000$

* Pentru alte teste în valoare de 10 puncte, N = 0 sau M = 0.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Se vor acorda 10 puncte din oficiu.

* h2. Exemplu

 
h2. Exemplu

table(example). |_. tractor2.in |_. tractor2.out |
| 3 3 2