==Include(page="template/taskheader" task_id="gard")==

==Include(page="template/taskheader" task_id="gard")==
 
O echipa de $K$ muncitori a fost angajata sa vopseasca un gard format din $N$ scanduri numerotate de la $1$ la $N$, de la stanga spre dreapta. Fiecare muncitor $i (1 ≤ i ≤ K)$ se aseaza in fata scandurii $S{~i~}$ si poate vopsi numai un interval compact (adica numerele de ordine ale scandurilor din interval sunt consecutive) avand maxim $L{~i~}$ scanduri, interval care trebuie sa contina scandura $S{~i~}$. Pentru fiecare scandura vopsita, acesta este platit cu suma $P{~i~}$. Din motive de eficienta, oricare 2 muncitori din echipa trebuie sa vopseasca intervale de scanduri disjuncte (adica oricare scandura a gardului poate fi vopsita de cel mult un membru al echipei).
Fiind conducatorul echipei de muncitori, dumneavoastra doriti sa determinati pentru fiecare membru al echipei intervalul de scanduri pe care acesta va trebui sa il vopseasca, astfel incat castigul total sa fie maxim. Castigul total este egal cu suma castigurilor realizate de fiecare membru al echipei. Castigul realizat de fiecare muncitor este egal cu numarul de scanduri vopsite de acesta inmultit cu $P{~i~}$ (pentru muncitorul cu numarul $i$).
 
h2. Cerinta
 
Scrieti un program care determina castigul maxim obtinut de cei $K$ muncitori.
 
h2. Date de Intrare
 
Fisierul de intrare $gard.in$ contine:
 
table(example). |gard.in | Semnificatie |
| N K
 L{~1~} P{~1~} S{~1~}
 L{~2~} P{~2~} S{~2~}
 ...
 L{~K~} P{~K~} S{~K~} | N - numarul de scanduri; K - numarul de muncitori
 L{~i~} - numarul maxim de scanduri ce pot fi vopsite de muncitorul cu numarul $i$
 P{~i~} - suma primita de muncitorul $i$ pentru fiecare scandura vopsita de acesta
 S{~i~} - scandura din gard in fata careia se aseaza muncitorul i |
 
h2. Date de Iesire
 
In fisierul $gard.out$ veti afisa castigul maxim obtinut de intreaga echipa de muncitori.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 16.000$
* $1 ≤ K ≤ 100$
* $1 ≤ P{~i~} ≤ 10.000$
* $1 ≤ L{~i~},S{~i~} ≤ N$
* Toate numerele $S{~i~}$ vor fi distincte.
* Nu trebuie vopsite neaparat toate cele $N$ scanduri ale gardului.
* Este permis ca unul sau mai multi dintre membrii echipei sa nu vopseasca nici o scandura, caz in care scandura in fata careia s-au asezat initial poate fi vopsita, eventual, de catre alt muncitor.
 
h2. Exemplu
 
table(example). |_. gard.in |_. gard.out |
| 8 4
3 2 2
3 2 3
3 3 5
1 1 7 | 17 |
 
h3. Explicatie
 
Muncitorul $1$ vopseste intervalul de scanduri $[1, 2]$; muncitorul $2$ vopseste intervalul de scanduri $[3, 4]$; muncitorul $3$ vopseste intervalul de scanduri $[5, 7]$; muncitorul $4$ nu vopseste nici o scandura.
 
==Include(page="template/taskfooter" task_id="gard")==
 
 

==Include(page="template/raw")==
 
Gard
 
 
 
O echipa de K muncitori a fost angajata sa vopseasca un gard format din N scanduri numerotate de la 1 la N, de la stanga spre dreapta. Fiecare muncitor i (1-L-i-L-K) se aseaza in fata scandurii S[i] si poate vopsi numai un interval compact (adica numerele de ordine ale scandurilor din interval sunt consecutive) avand maxim L[i] scanduri, interval care trebuie sa contina scandura S[i]. Pentru fiecare scandura vopsita, acesta este platit cu suma P[i]. Din motive de eficienta, oricare 2 muncitori din echipa trebuie sa vopseasca intervale de scanduri disjuncte (adica oricare scandura a gardului poate fi vopsita de cel mult un membru al echipei).
 
Fiind conducatorul echipei de muncitori, dumneavoastra doriti sa determinati pentru fiecare membru al echipei intervalul de scanduri pe care acesta va trebui sa il vopseasca, astfel incat castigul total sa fie maxim. Castigul total este egal cu suma castigurilor realizate de fiecare membru al echipei. Castigul realizat de fiecare muncitor este egal cu numarul de scanduri vopsite de acesta inmultit cu P[i] (pentru muncitorul cu numarul i).
 
h2. Cerinta
 
Scrieti un program care determina castigul maxim obtinut de cei K muncitori.
 
h2. Date de Intrare
 
Fisierul de intrare gard.in contine:
 
 
 
gard.in ]Semnificatie
N K N - numarul de scanduri; K - numarul de muncitori
 
L[1] P[1] S[1 L[i] - numarul maxim de scanduri ce pot fi vopsite de muncitorul cu numarul i
 
]L[2] P[2] S[2 P[i] - suma primita de muncitorul i pentru fiecare scandura vopsita de acesta
 
]... S[i] - scandura din gard in fata careia se aseaza muncitorul i
 
L[K] P[K] S[K
 
h2. Date de Iesire
 
In fisierul gard.out veti afisa castigul maxim obtinut de intreaga echipa de muncitori.
 
h2. Restrictii si precizari
 
. 1 <= N <= 16.000
 
. 1 <= K <= 100
 
. 1 <= P[i] <= 10.000
 
. 1 <= L[i],S[i] <= N
 
. Toate numerele S[i] vor fi distincte.
 
. Nu trebuie vopsite neaparat toate cele N scanduri ale gardului.
 
. Este permis ca unul sau mai multi dintre membrii echipei sa nu vopseasca nici o scandura, caz in care scandura in fata careia s-au asezat initial poate fi vopsita, eventual, de catre alt muncitor.
 
h2. Exemplu
 
gard.in gard.out Explicatie
8 4 17 muncitorul 1 vopseste intervalul de scanduri [1, 2]; muncitorul 2 vopseste intervalul de scanduri [3, 4]; muncitorul 3 vopseste intervalul de scanduri [5, 7]; muncitorul 4 nu vopseste nici o scandura.
 
3 2 2
 
3 2 3
 
3 3 5
 
1 1 7
 
 
==Include(page="template/taskfooter" task_id="gard")==

453