== include(page="template/taskheader" task_id="praslea") ==
Poveste şi cerinţă...
Prâslea cel Voinic trebuie să păzească grădina fermecată. El a primit de la Vrăjitorul din Oz o listă cu evenimentele ce urmează să aibă loc în gradină. Mai exact, Vrăjitorul l-a anunţat despre cei $N$ zmei care urmează să se plimbe prin gradină. Fiecare zmeu $i$ va intra în grădină la momentul de timp $A{~i~}$ şi va sta în grădină până în momentul de timp $B{~i~}$. Pentru a-şi dezvolta forţa de luptător, Prâslea Cel Voinic poate alege la orice moment de timp întreg un grup de zmei (dintre cei care se află în acel moment de timp în gradină) care urmează să-i fie adversari într-o luptă dreaptă, dar atât de scurtă încât durata ei se poate neglija. În această luptă, Prâslea se luptă cu toţi zmeii din grup deodată. Pentru fiecare zmeu $i$, Prâslea cunoaşte forţa $F{~i~}$ pe care o va acumula dacă se va lupta cu el. De asemenea pentru fiecare zmeu $i$ cunoaşte gradul de risc de a fi „accidentat”, $R{~i~}$, pe care îl presupune lupta cu acesta. Forţa totală pe care o acumulează Prâslea într-o luptă este suma forţelor acumulate de la fiecare zmeu din grupul ales, iar gradul total de risc pe care şi-l asumă este egal cu suma gradelor de risc ale fiecărui zmeu din grup. Fiind un tânăr cumpătat, Prâslea nu vrea să-şi asume vreodată un grad de risc total strict mai mare decat $Rmax$.
h2. Cerinta
Să se scrie un program care determină pentru Prâslea Cel Voinic care este forţa totală maximă pe care o poate acumula alegând într-un mod favorabil grupurile de zmei care îi vor fi adversari în luptă.
h2. Date de intrare
Fişierul de intrare $praslea.in$ ...
Fişierul de intrare $praslea.in$ va conţine pe prima linie numerele $N$ si $Rmax$. Următoarele $N$ linii vor conţine informaţiile despre zmei adunate de Vrăjitorul din Oz. Linia $i+1$ va conţine patru numere naturale separate printr-un singur spaţiu, A{~i~} B{~i~} F{~i~} şi R{~i~}, reprezentând informaţiile referitoare la zmeul $i$.
h2. Date de ieşire
În fişierul de ieşire $praslea.out$ ...
Fişierul de ieşire $praslea.out$ va conţine pe prima linie forţa totală maximă pe care o poate acumula Prâslea Cel Voinic.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1$ ≤ $N$, $Rmax$, $F{~i~}$, $R{~i~}$ ≤ $512$
* $1$ ≤ $A{~i~}$ ≤ $B{~i~}$ ≤ $2.000.000.000$
* Toate numerele din fişierul de intrare sunt naturale. În orice moment de timp Prâslea Cel Voinic poate alege doar un singur grup de zmei pe care îi va înfrunta în luptă
* Prâslea poate lupta cu zmeul $i$ care intră în grădina la momentul $A{~i~}$ şi iese la momentul $B{~i~}$ inclusiv în momentele $A{~i~}$ şi $B{~i~}$.
* Oricare zmeu poate fi „invitat” la luptă de mai multe ori pe parcursul perioadei în care stă în grădină.
h2. Exemplu
table(example). |_. praslea.in |_. praslea.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 2
1 2 2 1
2 3 2 1
| 8
|
h3. Explicaţie
...
La momentul de timp $1$ Prâslea se va lupta cu primul zmeu, acumulând o forta de valoare $2$. In momentul de timp $2$ se va lupta cu ambii zmei şi va acumula o forţă totală de valoare $4$. În momentul de timp $3$ se va lupta cu al doilea zmeu, acumulând o forţă de valoare $2$. În total, $2$ + $4$ + $2$ = $8$.
== include(page="template/taskfooter" task_id="praslea") ==
