praslea

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 $R_{max}$.

Cerință

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

Date de intrare

Fişierul de intrare praslea.in va conţine pe prima linie numerele $N$ si $R_{max}$. 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$.

Date de ieșire

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.

Restricții și precizări

• $1 \leq N, R_{max}, F_i, R_i \leq 512$
• $1 \leq A_i \leq B_i \leq 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ă.

Exemplu

praslea.in

2 2
1 2 2 1
2 3 2 1

praslea.out

8

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