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$

24 1 4
29 2 5
31 1 1

| 121
|