== include(page="template/taskheader" task_id="tractor2") ==
În oraşul Târgu Mureş, există un parc de distracţii mai puţin cunoscut. Atracţia principală este XTreme Tractor - un tractor de mare viteză, singurul care a mai rămas din seria sa de tractoare de mare viteză. Personalul parcului doreşte să gestioneze cât mai bine vizitatorii care se urcă în el.
În oraşul Târgu Mureş, există un parc de distracţii mai puţin cunoscut. Atracţia principală este $XTreme Tractor$ - un tractor de mare viteză, singurul care a mai rămas din seria sa de tractoare de mare viteză. Personalul parcului doreşte să gestioneze cât mai bine vizitatorii care se urcă în el.
Înainte de îmbarcare, lumea se aşază la una dintre cele două cozi de la intrare: prima coadă este destinată doar persoanelor venite singure, iar a doua coadă este destinată doar persoanelor venite în grupuri de câte $2$, $3$ sau $4$. Persoanele dintr-un grup nu se pot separa şi se vor da cu tractorul împreună. Persoanele din prima coadă şi grupurile din a doua coadă se aşază în coada corespunzătoare la diverse momente de timp, dar, $în cadrul aceleiaşi cozi$, vor exista doar timpi de intrare $distincţi$. Pe parcursul zilei, vor intra $N$ persoane în prima coadă şi $M$ grupuri în a doua coadă. În plus, pe lângă timpul de intrare în coada corespunzătoare, se mai cunoaşte, pentru fiecare persoană şi pentru fiecare grup, $durata de îmbarcare$.
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.
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
* $0 ≤ N ≤ 3 000$
* $0 ≤ M ≤ 1 000$
* $1 ≤ P ≤ 109$
* $1 ≤ t, c ≤ 109$
* $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. $
* 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. $
* h2. Exemplu $
* 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.
* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".
h2. Exemplu
table(example). |_. tractor2.in |_. tractor2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3 2
1 1 1
2 2 1
3 4 1
4 3 2
10 1 1
11 1 1
| 20
|
| 4 4 30
13 2 2
13 1 3
16 2 4
18 2 7
22 1 3
24 1 4
29 2 5
31 1 1
| 121
|
h3. Explicaţie
...
Următorul tabel explică maniera optimă de îmbarcare pentru primul exemplu:
table(explicatie). |_. timp |_. eveniment |
| 1
| În prima coadă, intră o persoană cu durata de îmbarcare $1$.
|
| 2
| În a doua coadă, intră un grup de $2$ vizitatori cu durata de îmbarcare $1$.
|
| 3
| În a doua coadă, intră un grup de $4$ vizitatori cu durata de îmbarcare $1$.
|
| 4
| În a doua coadă, intră un grup de $3$ vizitatori cu durata de îmbarcare $2$.
|
| 10
| În prima coadă, intră o persoană cu durata de îmbarcare $1$.
Se aleg pentru prima cursă persoanele ajunse la timpii $1$ şi $10$ şi grupul ajuns la timpul $2$.
Durata de îmbarcare este $max(1,1,1)=1$.
|
| 11
| În prima coadă, intră o persoană cu durata de îmbarcare $1$.
Îmbarcarea e terminată şi începe prima cursă cu tractorul.
|
| 13
| Se termină prima cursă cu tractorul.
Se alege pentru a doua cursă grupul ajuns la timpul $3$.
Durata de îmbarcare este $max(1)=1$.
|
| 14
| Îmbarcarea e terminată şi începe a doua cursă cu tractorul.
|
| 16
| Se termină a doua cursă cu tractorul.
Se aleg pentru a treia cursă persoana ajunsă la timpul $11$ şi grupul ajuns la timpul $4$.
Durata de îmbarcare este $max(1,2)=2$.
|
| 18
| Îmbarcarea e terminată şi începe a treia cursă cu tractorul.
|
| 20
| Se termină a treia cursă cu tractorul.
Toate persoanele şi grupurile s-au dat cu tractorul, deci răspunsul e $20$.
|
== include(page="template/taskfooter" task_id="tractor2") ==
