6. Just načas

Jednuho dňa došla žatva, tak bulo treba makac. Traktorista Janči téhož rána nakopol mašinu a iď ho aj s vlečkú krs pole naberac pokosenô úrodu od kombajnú. Traktor si to šine solídnym tempem, ale len po vyjetých štrekách, šak by zmršil sceblá keby né, to by zase kluci džubali. Taký kombajnista je pilnô chľapa, ale sedlák: chodzí si po poli a žne, a keď má už v kombajnu plnô, chce friškom vidzec traktor, kerý to šicko veme. Tož keď tam žádny není, tak to just kydne do stredu pola a idze dom – ať si to ktosi pozberá odtál, šak si nebude on tu kečku paric o kus déle a stác jak taký cicimbrus. Janči s traktorem to ze zeme zebrac neví, tož sa budze musec jutro nadrapovac s lopatú. Z tého dúvodu by chtil čo najvecej ich scihnúc už dneskáj.

Úloha

Traktor sa pohybuje po štvorcovom poli s plochou \(h\) hektárov. Môže však chodiť len po vyjazdených cestách, pričom každých 100 metrov po strane poľa jedna takáto cesta začína a pokračuje kolmo na stranu poľa až na druhý koniec – pole má teda tvar pravoúhlej mriežky so stranou 100 metrov. Zároveň je pole pekné – dĺžka jeho strany je tiež násobkom 100 metrov a je dokonca zarovnané so svetovými stranami. Jazdiť po okraji poľa sa samozrejme dá. Traktor má maximálnu rýchlosť chôdze, teda akurát takú, že tých 100 metrov prejde presne za minútu. Janči začína pracovať ráno na severozápadnom okraji poľa.

Na poli sa tiež nachádza \(n\) kombajnistov, ktorí po dokončení svojej práce chcú vyprázdniť nádrž na zrno do vlečky, ktorú traktor ťahá za sebou. Keďže Janči kombajnistov a ich pracovné návyky dobre pozná, vie presne, kedy bude ktorý z nich končiť a kde sa pritom bude nachádzať. Ak sa mu podarí byť v danom čase na rovnakom mieste, ako kombajnista, okamžite naberie zrno a pokračuje ďalej. Ak to ale nestihne, nahnevaný kombajnista zrno vysype na pole, takže sa poň Janči bude musieť vrátiť zajtra a nalopatovať ho do vlečky ručne – chce teda, aby bol počet týchto nestihnutých vysypaní čo najmenší. Janči si je istý, že žiadni dvaja kombajnisti neskončia v rovnakom čase.

Formát vstupu

Na prvom riadku dostanete medzerou oddelené čísla \(h\) a \(n\) – plochu poľa v hektároch a počet kombajnistov brázdiacich pole. Nasleduje \(n\) riadkov, každý z nich obsahuje tri medzerou oddelené čísla: \(t_i\), \(x_i\), \(y_i\) – čas v minútach od rána, kedy daný kombajnista vysype svoj náklad a jeho súradnice v metroch od severozápadného okraja poľa v danom momente.

Platí, že \(1 \leq t_i \leq 10^9\) a bod \(x_i, y_i\) leží na priesečníku nejakých dvoch ciest. Všetci kombajnisti na vstupe sú zoradení vzostupne podľa časov sypania nákladu. Žiadni dvaja kombajnisti nesypú náklad v rovnakom čase.

Formát výstupu

Na výstup vypíšte jedno číslo: najmenší možný počet kombajnistov, ktorých náklad nestihne Janči zozbierať, ak bude po poli prechádzať optimálne. Nezabudnite na znak konca riadku.

Obmedzenia

Existujú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:

Príklad

Input:

100 5
11 300 700
12 900 300
13 500 700
17 800 0
20 600 0

Output:

2

Janči môže tesne stihnúť prvého alebo druhého kombajnistu. Ak si vyberie prvého, stihne aj tretieho, ale nestihne štvrtého. Naopak, ak si vyberie druhého, stihne štvrtého, ale nie tretieho. Piaty kombajnista však jednoznačne určuje, čo musí Janči spraviť – dá sa ho stihnúť, ak predtým bude načas pri štvrtom, ale nie, ak bude pri treťom. Optimálne je teda vyzdvinúť náklad od kombajnistov 2, 4 a 5, odignorovaní zostanú dvaja: 1 a 3.

Trikové okienko

Vedeli ste o tom, že v Pythone je vyhodnocovanie kódu v globálnom skôpe pomalšie než vyhodnocovanie kódu v skôpe funkcie?¹ Pridaním iba dvoch riadkov (hlavička funkcie a jej volanie) viete častokrát kód mnohonásobne zrýchliť. Možno sa vám to v tejto úlohe môže hodiť. Nie vždy to ale pomôže. V každom prípade to odporúčame na tejto a aj iných KSP úlohách vyskúšať. Budeme radi ak nám o svojich zisteniach napíšete v popise. Aj my sme zvedaví, ako často a ako veľmi to vie pomôcť. Nič však nepokazíte ak budete vyššie KSP úlohy riešiť v C++, keďže optimalizácie ktoré nám dáva gcc častokrát robia kúzla.