e-olymp
Задачі

Розклад від "Дієз-Продукт"

Розклад від "Дієз-Продукт"

Після завершення комп’ютеризації начального закладу, коли комп’ютери було встановлено у кожному кабінеті, директор та його заступник з навчальної частини зрозуміли, що без програми "Розклад" фірми "Дієз-продукт" їм аж ніяк не обійтись.

Судіть самі. У навчальному закладі N кабінетів, у яких потрібно провести K занять. Але біда в тому, що техніка у всіх кабінетах різна – тому у різних кабінетах можна працювати різний час. Згідно вимог техніки безпеки та санітарних вимог у кожному кабінеті встановлено графік обов’язкових прибирань протягом певного часу (свого для кожного кабінету, так як площа кабінетів різна, та й прибирають техпрацівники різного віку) після проведення вказаної кількості занять (знову ж таки, можливо і різної для різних кабінетів).

Допоможіть адміністрації навчального закладу визначити мінімальний час, за який вони зможуть провести всі заплановані заняття.

Вхідні дані

У першому рядку через пропуск задано два числа: кількість кабінетів N та кількість занять K. У наступних N рядках через пропуск задано тривалість проведення заняття у i-му кабінеті Ui, кількість уроків у кабінеті Ci, після яких робиться технічна перерва, та її тривалість Ti.

1N50, 1K2000, 30Ui120, 1Ci100, 10Ti50.

Вихідні дані

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

Ліміт часу 1.5 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 100
10 30 40
30 100 30
20 50 20
Вихідні дані #1
570