Склад
Хлопчик Вася прийшов з мамою у продуктовий магазин. Вони вирішили купити торт «Прага», і мама сказала про це продавцю. Продавець пішов кудись у сусідню кімнату без торту, а повернувся з тортом, що несказанно здивувало Васю — ще б пак, адже не кожен день він бував у кімнаті, де з'являються торти. Він вирішив з усіх сторін дослідити цей феномен, для чого вговорив маму купити інший торт. У той момент, коли продавець пішов за іншим тортом у сусідню кімнату, Вася непомітно просковзнув за ним. І його очам відкрилось дивовижне видовище: він попав на склад тортів. Ось стоять «Бджілки», ось «Політ», ось «Київські»… Але Вася не здригнувся перед такими щедротами, і вирішив знайти на складі найсмачніший торт. Проте він і не підозрював, что торти ретельно охороняються, і що до нього вже сотні хлопчиків проникали на цей склад — але жоден не повернувся додому… Будучи повністю не поінформованим відносно небезпек, що його очікують, Вася став досліджувати склад сантиметр за сантиметром — і як тільки він випадково наступив на червону мітку на підлозі, підлога під ним провалилася і Вася опинився у глибокій ямі (глибина ями складала 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).
Вихідні дані
У вихідний файл виведіть минимальне число годин, яке потрібно Васі, щоб врятуватись. У випадку якщо Вася приречений, виведіть, яку максимальну кількість годин він зможе протянути.