Після завершення комп’ютеризації начального закладу, коли комп’ютери було встановлено у кожному кабінеті, директор та його заступник з навчальної частини зрозуміли, що без програми "Розклад" фірми "Дієз-продукт" їм аж ніяк не обійтись. Судіть самі. У навчальному закладі \textbf{N} кабінетів, у яких потрібно провести \textbf{K} занять. Але біда в тому, що техніка у всіх кабінетах різна -- тому у різних кабінетах можна працювати різний час. Згідно вимог техніки безпеки та санітарних вимог у кожному кабінеті встановлено графік обов’язкових прибирань протягом певного часу (свого для кожного кабінету, так як площа кабінетів різна, та й прибирають техпрацівники різного віку) після проведення вказаної кількості занять (знову ж таки, можливо і різної для різних кабінетів). Допоможіть адміністрації навчального закладу визначити мінімальний час, за який вони зможуть провести всі заплановані заняття. \InputFile У першому рядку через пропуск задано два числа: кількість кабінетів \textbf{N} та кількість занять \textbf{K}. У наступних \textbf{N} рядках через пропуск задано тривалість проведення заняття у \textit{\textbf{i}}-му кабінеті \textbf{U_i}, кількість уроків у кабінеті \textbf{C_i}, після яких робиться технічна перерва, та її тривалість \textbf{T_i}. \textbf{1} ≤ \textbf{N} ≤ \textbf{50}, \textbf{1} ≤ \textbf{K} ≤ \textbf{2000}, \textbf{30} ≤ \textbf{U_i} ≤ \textbf{120}, \textbf{1} ≤ \textbf{C_i} ≤ \textbf{100}, \textbf{10} ≤ \textbf{T_i} ≤ \textbf{50}. \OutputFile Єдине число - мінімальний час, за який буде проведено всі заняття.