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