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

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

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

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

Вхідні дані

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

$1\le N\le 50$, $1\le K\le 2000$, $30\le U_i\le 120$, $1\le C_i\le 100$, $10\le T_i\le 50$.

Вихідні дані

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

Приклади