Problem description

Pan Wiesio znany jest z tego, że ,,robi u siebie jak u siebie’’, dlatego przed następnym remontem chciałby dowiedzieć się, ile uda mu się na nim zaoszczędzić, wykonując go samemu. Remont polega na położeniu dokładnie M metrów kwadratowych płytek, oczywiście bez krzyżaczków. Na Grochowie dostępnych jest N majstrów, i-ty z nich ma cennik składający się z trzech liczb:

• D_i – opłata początkowa,
• C_i – koszt położenia jednego metra kwadratowego płytek,
• Z_i – limit powyżej którego majster nie jest w stanie już pracować, tzn. może on położyć co najwyżej Z_i metrów kwadratowych płytek.

Twoim zadaniem jest obliczenie jaką kwotę zaoszczędzi pan Wiesio, czyli ile wyniósłby minimalny koszt wykonania remontu. Możesz założyć, że dane są dobrane tak, że wykonanie remontu jest zawsze możliwe.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite N i M, będące odpowiednio liczbą majstrów oraz powierzchnią konieczną do wyremontowania. W kolejnych N wierszach znajduje się opis cenników majstrów. Każdy cennik składa się z trzech liczb całkowitych: D_i, C_i oraz Z_i, tak jak opisano w treści zadania.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca minimalnym kosztem wykonania remontu.

Ograniczenia

1 ≤ N, M ≤ 4000, 1 ≤ D_i, C_i ≤ 10⁷, 1 ≤ Z_i ≤ M.

Przykład

5 20
5 2 5
1 4 4
3 2 5
9 1 4
2 4 5

68