Anbar
Uşaq Vasya anası ilə birlikdə ərzaq mağazasına gəldi. Onlar "Praqa" tortu almağa qərar verdilər və ana bunu satıcıya bildirdi. Satıcı tortsuz qonşu otağa getdi, amma tortla geri qayıtdı, bu da Vasyanı çox təəccübləndirdi — axı hər gün tortların peyda olduğu otaqda olmurdu. O, bu fenomeni araşdırmağa qərar verdi və anasını başqa bir tort almağa razı saldı. Satıcı başqa tort üçün qonşu otağa gedəndə, Vasya gizlicə onun arxasınca sürüşdü. Gözləri qarşısında möhtəşəm bir mənzərə açıldı: o, tort anbarına düşdü. Burada "Arılar", "Uçuş", "Kiyev" tortları dayanır... Amma Vasya bu qədər bolluq qarşısında sarsılmadı və anbarda ən dadlı tortu tapmağa qərar verdi. Lakin o, tortların diqqətlə qorunduğunu və ondan əvvəl yüzlərlə oğlanın bu anbarda olduğunu, lakin heç birinin evə qayıtmadığını bilmirdi... Tamamilə gözlənilən təhlükələrdən xəbərsiz olan Vasya anbarda santimetr-santimetr araşdırmağa başladı — və təsadüfən döşəmədəki qırmızı işarəyə basan kimi, döşəmə onun altında çökdü və Vasya dərin bir çuxura düşdü (çuxurun dərinliyi D fut idi, 2 ≤ D ≤ 100). Vasya pioner idi və buna görə də heç çaşmadı, yaranmış vəziyyətdən çıxış yolu axtarmağa başladı. Məlum oldu ki, bu çuxura vaxtaşırı tortlar atılır, Vasya isə bu tortları ya yeyə bilər, ya da bir böyük yığın halında toplaya bilər, bu zaman hər tortu ya tamamilə yemək, ya da ümumiyyətlə yeməmək olar. Çuxurdan çıxmaq üçün Vasyanın D hündürlüyündə bir yığın düzəltməsi lazımdır. Bu zaman Vasyanın gücü sonsuz deyil və çuxurda daha uzun yaşamaq üçün ona yemək lazımdır, bu yemək isə həmin tortlardır ki, o, onları lazım olan yığının hündürlüyünü artırmaq üçün istifadə edə bilər. Çuxurun divarındakı gizli yazıları deşifrə edərək, Vasya hansı tortların və nə vaxt aşağı atılacağını öyrəndi. Vasyaya xilas olmağa kömək edin!
Vasyanın çuxura düşdüyü an 0 vaxtı hesab edəcəyik və onun başlanğıcda 10 saatlıq gücü var. Qeyd edək ki, əgər Vasyanın, məsələn, 3 saatlıq gücü qalıbsa və növbəti tort çuxura dəqiq 3 saat sonra atılacaqsa, Vasya dərhal yeməyə başlaya bilər və aclıqdan ölməz.
Giriş verilənləri
Giriş faylının əvvəlində çuxurun dərinliyi olan D və çuxura atılan tortların sayı olan G tam ədədləri verilir (1 ≤ G ≤ 100). Sonra atılan tortların təsvirləri, hər tort üçün üç tam ədəd verilir: T — bu tortun çuxura atılacağı vaxt saatla (0 < T ≤ 1000), F — Vasya bu tortu yeyəndə əldə edəcəyi əlavə həyat saatlarının sayı (1 ≤ F ≤ 30) və H — bu tortun hündürlüyü futla (1 ≤ H ≤ 25).
Çıxış verilənləri
Çıxış faylında Vasyanın xilas olması üçün lazım olan minimal saat sayını yazın. Əgər Vasya məhkumdursa, onun maksimum neçə saat davam edə biləcəyini yazın.