Təhsil müəssisələrinin komyuterləşdirilməsi başa çatdıqdan sonra hər bir kabinetdə kompyuter quraşdırıldı, direktor və onun tədris işləri üzrə müavini anladılar ki, “Diez-Produkt” firmasının “Cədvəl” proqramı olmadan keçinə bilməyəcəklər. Özünüz mühakimə edin. Tədris müəssisəsində olan \textbf{N }sayda kabinetdə \textbf{K} sayda dərs keçmək lazımdır. Bəla bundadır ki, texnika bütün kabinetlərdə fərqlidir, ona görə də müxtəlif kabinetlərdə müxtəlif vaxtlarda işləmək olar. Texniki təhlükəsizlik qaydalarına və sanitar normalara görə hər kabinetdə müəyyən müddət ərzində kabinetin təmizlənməsi qrafiki müəyyənləşdirilib( hər kabinetin öz xüsusiyyəti var, belə ki, kabinetlərin sahəsi müxtəlifdir, bəli, müxtəlif yaşda olan texniki işçilər təmizləyirlər). Bütün planlaşdırılmış məşğələlərin keçirilə biləcəyi ən qısa vaxtı müəyyənləşdirməkdə tədris müəssisəsinin rəhbərliyinə kömək edin. \InputFile Birinci sətirdə aralarında boşluq işarəsi olmaqla iki ədəd - kabinetlərin \textbf{N} sayı və məşğələlərin \textbf{K} sayı verilir. Sonrakı \textbf{N} sayda sətrin hər birində aralarında boşluq işarəsi olmaqla\textbf{ i-}ci kabinetdə\textbf{ }keçilən məşğələnin \textbf{U}\textit{\textbf{_i}} müddəti, dərslərin \textbf{C}\textit{\textbf{_i}} sayı, həmin dərsdən sonra gələn texniki tənəffüsün\textbf{ T}\textit{\textbf{_\{i \}}}müddəti verilir: \textbf{1} ≤ \textbf{N} ≤ \textbf{50}, \textbf{1} ≤ \textbf{K} ≤ \textbf{2000}, \textbf{30} ≤ \textbf{U}\textit{\textbf{_i}} ≤ \textbf{120}, \textbf{1} ≤ \textbf{C}\textit{\textbf{_i}} ≤ \textbf{100}, \textbf{10} ≤ \textbf{T}\textit{\textbf{_i}} ≤ \textbf{50}. \OutputFile Yeganə ədəd - bütün məşğələlərin keçirilməsi üçün minimum vaxt.