== include(page="template/taskheader" task_id="praslea") ==

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$.

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

h2. Restricţii
* $1$ ≤ $N$, $Rmax$, $F{~i~}$, $R{~i~}$ ≤ $512$

* $1$ ≤ $A{~i~}$ ≤ $B{~i~}$ ≤ $2000000000$

* $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ă.

3940