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

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

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

1 ≤ N ≤ 50, 1 ≤ K ≤ 2000, 30 ≤ Ui ≤ 120, 1 ≤ Ci ≤ 100, 10 ≤ Ti ≤ 50.

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

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