После завершения компьютеризации учебного заведения, когда компьютеры были установлены в каждом кабинете, директор и его заместитель по учебной части поняли, что без программы "Расписание" фирмы "Диез-продукт" им ну никак не обойтись.
Судите сами. В учебном заведении N кабинетов, в которых нужно провести K занятий. Но вся беда в том, что техника во всех кабинетах разная – поэтому в разных кабинетах можно работать разное время. Согласно требований техники безопасности и санитарных норм в каждом кабинете установлен график обязательных уборок на протяжении определенного времени (своего для каждого кабинета, так как площадь кабинетов разная, да и убирают техработники разного возраста) после проведения указанного количества занятий (опять же, возможно и разного для разных кабинетов).
Помогите администрации учебного заведения определить минимальное время, за какое они смогут провести все запланированные занятия.

   Входные данные

   В первой строке через пробел задано два числа: количество кабинетов N и количество занятий K. В последующих N строках через пробел задано продолжительность проведения занятия в i-м кабинете U_i, количество уроков в кабинете C_i, после которых производится технеский перерыв, и его продолжительность T_i.

   1 ≤ N ≤ 50, 1 ≤ K ≤ 2000, 30 ≤ U_i ≤ 120, 1 ≤ C_i ≤ 100, 10 ≤ T_i ≤ 50.

   Выходные данные

   Единственное число - минимальное время, за кокое будут проведены все занятия.