Мальчик Вася пришёл с мамой в продуктовый магазин. Они решили купить торт <<Прага>>, и мама сказала об этом продавцу. Продавец ушёл куда-то в соседнюю комнату без торта, а вернулся с тортом, что несказанно удивило Васю --- ещё бы, ведь не каждый день он бывал в комнате, где появляются торты. Он решил всесторонне исследовать этот феномен, для чего уговорил маму купить другой торт. В тот момент, когда продавец пошёл за другим тортом в соседнюю комнату, Вася незаметно проскользнул за ним. И его глазам открылось умопомрачительное зрелище: он попал на склад тортов. Вот стоят <<Пчелки>>, вот <<Полёты>>, вот <<Киевские>>… Но Вася не дрогнул перед таким изобилием, и решил найти на складе самый вкусный торт. Но он и не подозревал, что торты тщательно охраняются, и что до него уже сотни мальчиков пробрались на этот склад --- но ни один не вернулся домой… Будучи в полном неведении относительно подстерегающих его опасностей, Вася стал исследовать склад сантиметр за сантиметром --- и как только он случайно наступил на красную метку на полу, пол под ним провалился и Вася оказался в глубокой яме (глубина ямы составила \textit{\textbf{D}} футов, \textbf{2} ≤ \textit{\textbf{D}} ≤ \textbf{100}). Вася был пионером, и поэтому совсем-совсем не растерялся, а стал искать выход из сложившейся ситуации. Как оказалось, время от времени в эту яму сбрасывали торты, которые Вася мог либо съедать, либо складывать в одну большую кучу, при этом каждый торт можно только либо съесть целиком, либо вообще не есть. Для того чтобы выбраться, Васе необходимо сложить кучу высотой \textit{\textbf{D}}. При этом силы Васи не безграничны, и чтобы прожить в яме подольше, ему необходима еда, в качестве которой выступают те самые торты, которые он мог бы использовать для увеличения высоты спасительной кучи. Расшифровав секретные записи на стене ямы, Вася узнал, какие торты и когда будут сброшены вниз. Помогите Васе спастись! Будем считать, что Вася упал в яму в момент времени \textbf{0}, а сил у него изначально хватит на \textbf{10} часов. Заметим при этом, что если у Васи осталось сил, скажем, на \textbf{3} часа, а следующий торт будет сброшен в яму ровно через \textbf{3} часа, то Вася сможет начать есть немедленно и не умрёт от голода. \InputFile В начале входного файла заданы целые числа \textit{\textbf{D}} --- глубина ямы, и \textit{\textbf{G}} --- количество сбрасываемых в яму тортов (\textbf{1} ≤ \textit{\textbf{G}} ≤ \textbf{100}). Далее записаны описания сбрасываемых тортов, по три целых числа на торт: \textit{\textbf{T}} --- момент времени в часах, когда этот торт будет сброшен в яму (\textbf{0} < \textit{\textbf{T}} ≤ \textbf{1000}), \textit{\textbf{F}} --- количество дополнительных часов жизни, которые Вася получит, съев этот торт (\textbf{1} ≤ \textit{\textbf{F}} ≤ \textbf{30}), и \textit{\textbf{H}} --- высота этого торта в футах (\textbf{1} ≤ \textit{\textbf{H}} ≤ \textbf{25}). \OutputFile В выходной файл выведите минимальное число часов, которое потребуется Васе, чтобы спастись. В случае если Вася обречён, выведите, какое максимальное число часов он сможет протянуть.