Vedúci po veľmi dlhej dobe začali upratovať kostýmy zo sústredení. Všetky boli v neoptimálnom stave. Boli zablatené, špinavé a podobne. Preto ich bolo potrebné oprať. Potom ale museli vyschnúť. Na to sme využili dve laná pri matfyze, na ktoré sme jednotlivé kostýmy zavesili.

Úloha

Vedúci potrebujú usušiť $n$ kostýmov. Máme $2$ rovnako dlhé rovnobežné laná dlhé $l$, na ktorých sa budú kostýmy sušiť. $i$-ty kostým má šírku $w_i$, zaberie teda $w_i$ miesta na lane. Každý kostým môžeme sušiť na jednom alebo na oboch lanách. Časy sušenia sú $t_{i1}$ (na jednom lane) a $t_{i2}$ (na oboch lanách). Platí, že každý kostým sa na oboch lanách vysuší rýchlejšie ako len na jednom. Ako najrýchlejšie vieme vysušiť všetky kostýmy iba na týchto dvoch lanách? Všetky kostýmy musíme zavesiť už na začiatku.

Formát vstupu

Na prvom riadku vstupu sú dve medzerou oddelené čísla $n$ a $l$, kde $n$ je počet kostýmov a $l$ je dĺžka lán. Potom nasleduje $n$ riadkov, kde každý riadok obsahuje tri medzerou oddelené čísla - $w_i$, $t_{i1}$ a $t_{i2}$, kde $w_i$ je šírka $i$-tého kostýmu, $t_{i1}$ je čas sušenia na jednom lane a $t_{i2}$ je čas sušenia na oboch lanách. Pre každý kostým platí $t_{i1} > t_{i2}$.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jedno číslo - minimálny čas, po ktorom sa všetky kostýmy usušia. Ak kostýmy nie je možné vysušiť, vypíšte -1.

Príklady

5 12
4 9 3
3 9 2
2 9 3
4 8 5
4 10 1

9

Posledný kostým zavesíme na obe laná a zvyšné musia byť zavesené na jednom lane, aby sa zmestili. Napríklad zavesíme prvý a druhý kostým na prvé lano a tretí so štvrtým na druhé lano.

3 10
8 3 2
7 9 2
7 8 3

-1

Kostýmy nemáme ako usušiť - nezmestia sa na laná