Розклад від "Дієз-Продукт"
Розклад від "Дієз-Продукт"
Після завершення комп’ютеризації начального закладу, коли комп’ютери було встановлено у кожному кабінеті, директор та його заступник з навчальної частини зрозуміли, що без програми "Розклад" фірми "Дієз-продукт" їм аж ніяк не обійтись.
Судіть самі. У навчальному закладі 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.
Вихідні дані
Єдине число - мінімальний час, за який буде проведено всі заняття.
Приклад
3 100 10 30 40 30 100 30 20 50 20
570