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