eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расписание от "Диез-Продукт"

Расписание от "Диез-Продукт"

Лимит времени 1.5 секунда
Лимит использования памяти 64 MiB

После завершения компьютеризации учебного заведения, когда компьютеры были установлены в каждом кабинете, директор и его заместитель по учебной части поняли, что без программы "Расписание" фирмы "Диез-продукт" им ну никак не обойтись.Судите сами. В учебном заведении 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.

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

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

Пример

Входные данные #1
3 100
10 30 40
30 100 30
20 50 20
Выходные данные #1
570