Firma testuje technologię otrzymywania antymaterii wykorzystywanej jako paliwo w międzyplanetarnym statku kosmicznym. Antymateria powstaje w wyniku specjalnych eksperymentów w reaktorze.

Znanych jest $n$ typów eksperymentów prowadzących do otrzymania antymaterii. W wyniku eksperymentu typu $i$ do pojemnika wyjściowego reaktora trafia od $l_i$ do $r_i$ gramów antymaterii. Ze względów bezpieczeństwa nie wolno gromadzić w pojemniku więcej niż $a$ gramów antymaterii.

Koszt przeprowadzenia eksperymentu typu $i$ wynosi $c_i$, a wartość jednego grama otrzymanej antymaterii wynosi $10^9$.

Jeżeli po przeprowadzeniu eksperymentów w pojemniku znajduje się $t$ gramów antymaterii, a łączne koszty eksperymentów w reaktorze wyniosły $s$, zysk określa wzór $t\cdot10^9-s$. Firma musi opracować strategię przeprowadzania eksperymentów, która maksymalizuje zysk możliwy do zagwarantowania.

W zależności od wyników poprzednich eksperymentów strategia określa, jaki typ eksperymentu należy przeprowadzić, albo podejmuje decyzję o zakończeniu eksperymentów. Strategia pozwala zagwarantować zysk $x$, jeśli dla dowolnych wyników eksperymentów, po pierwsze, w pojemniku reaktora znajduje się nie więcej niż $a$ gramów antymaterii, a po drugie, zysk wynosi co najmniej $x$.

Na przykład załóżmy, że możliwy jest tylko jeden typ eksperymentu, wytwarzający od $4$ do $6$ gramów antymaterii, jego koszt wynosi $10$, a pojemność pojemnika to $17$ gramów. Wtedy po dwukrotnym przeprowadzeniu eksperymentu w pojemniku może znajdować się od $8$ do $12$ gramów antymaterii. Jeżeli otrzymano $12$ gramów, nie można już przeprowadzić kolejnego eksperymentu, ponieważ w przypadku otrzymania $6$ gramów pojemnik mógłby się przepełnić. W pozostałych przypadkach można przeprowadzić eksperyment po raz trzeci i otrzymać od $12$ do $17$ gramów antymaterii. W najgorszym przypadku trzeba przeprowadzić eksperyment trzykrotnie, ponosząc łączny koszt $30$, a zysk wyniesie $(12\cdot10^9-30)=11\,999\,999\,970$.

Należy napisać program wyznaczający maksymalny zysk $x$, który można zagwarantować.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite: $n$, liczbę typów eksperymentów, oraz $a$, maksymalną dopuszczalną ilość antymaterii w pojemniku, gdzie $1\le n\le100$ i $1\le a\le2\,000\,000$.

Każdy z następnych $n$ wierszy zawiera trzy liczby całkowite $l_i$, $r_i$ i $c_i$: odpowiednio minimalną i maksymalną ilość antymaterii otrzymywanej w wyniku eksperymentu typu $i$ oraz koszt eksperymentu tego typu, gdzie $1\le l_i\le r_i\le a$ i $1\le c_i\le100$.

Wyjście

Wyjście powinno zawierać jedną liczbę całkowitą: maksymalny zysk $x$, który można zagwarantować.

Przykład

Wejście 1

1 17
4 6 10

Wyjście 1

11999999970

Wejście 2

2 11
2 2 100
3 5 5

Wyjście 2

9999999890

Podzadania