D - Festivalové leto II

Blíži sa leto. A to je obdobie plné rôznych festivalov a akcií. Jožko si povedal, že sa toto leto chce zúčastniť toľko festivalov, koľko sa len dá. Problém však je, že niektoré akcie a festivaly sa konajú súbežne alebo sa termíny ich konania prekrývajú. Ktoré festivaly by si mal Jožko vybrať, ak chce navštíviť čo najviac festivalov? Poznamenajme, že ak sa Jožko rozhodne, že na nejaký festival pôjde, tak tam ostane po celú dobu trvania festivalu. Ak teda festival, ktorého sa zúčastní, končí v 30. deň leta, najbližší ďalší festival, ktorého sa zúčastní, môže začínať až v 31. deň leta.

Jožko ako študent nemá peňazí nazvyš. No a vstupenky na festivaly a akcie nie sú tiež zadarmo. Aby neminul viac peňazí ako môže, Jožko sa rozhodol, že si stanoví pevnú sumu S, za ktorú nepôjde. Suma S je ohraničenie pre súčet cien vstupeniek tých festivalov, ktoré sa Jožko počas leta rozhodne navštíviť.

Úloha

Vytvorte program, ktorý pre zadanú množinu festivalov vypočíta maximálny počet festivalov, ktorých sa môže Jožko počas leta zúčastniť a zároveň súčet cien vstupeniek na ne nepresahuje stanovenú hranicu S.

Vstup

Prvý riadok vstupu obsahuje 2 čísla: N a S. Prirodzené číslo N (1 ≤ N ≤ 80) vyjadruje počet festivalov, ktoré sa konajú počas leta, a číslo S je maximálna suma v celých eurách, ktorú je Jožko ochotný na festivaly počas leta minúť. Nasleduje N riadkov s údajmi o jednotlivých festivaloch. Každý festival je popísaný trojicou medzerami oddelených čísel: začiatočný deň, koncový deň a cena vstupenky. Začiatočný a koncový deň sú poradové čísla dňa v lete (t.j. dni sú označené ako 0, 1, 2, 3, ...,), t.j. začiatočný a koncový deň sú nezáporné čísla menšie ako 2000. Cena vstupenky je nanajvýš 50 EUR. Ak je vstup bezplatný, tak cena je 0 EUR. Ceny sú v celých eurách.

Výstup

Maximálny počet festivalov, ktorých sa Jožko vie zúčastniť pri zohľadnení jeho finančného limitu. Výstup ukončte znakom nového riadku.

Príklad

Vstup:

10 48
35 37 37
6 14 34
13 15 4
39 39 31
6 14 24
48 54 15
31 35 28
22 24 31
42 51 12
37 46 16

Výstup:

3