tractor2

Tractor2

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.

Fişierul de intrare $tractor2.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.

Fişierul de ieşire $tractor2.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

* $1 ≤ P ≤ 1 000 000 000$
* $1 ≤ t, c ≤ 1 000 000 000$
* $1 ≤ d ≤ 4$

* Rezultatul se poate reprezenta pe un întreg de 64 de biţi cu semn.

* Rezultatul se poate reprezenta pe un întreg de $64$ de biţi cu semn.

* Deplasarea în coadă şi coborârea din tractor se întâmplă instantaneu.
* Se garantează că întotdeauna există o modalitate validă pentru ca toate persoanele şi grupurile din cele două cozi să se poată urca în tractor.
* Fiecare persoană sau grup se pot da cu tractorul o singură dată.

* Pentru unele teste în valoare de 10 puncte, N+M ≤ 18.
* 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.

* Pentru unele teste în valoare de $10$ puncte, $N+M ≤ 18$.
* 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.
* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".

h2. Exemplu