Hiperaktiv Qız#3752
Helen çox enerjili bir qızdır. O, günün hər anında məşğul olmaq üçün ən azı bir fəaliyyətin olmasını istəyir. Fəaliyyətlərin vaxt baxımından üst-üstə düşməsi onu narahat etmir, yetər ki, günün hər anı üçün bir fəaliyyət planlaşdırılmış olsun.
Helen günü xüsusi bir şəkildə bölüb. Gün 0 vaxtında başlayır və M vaxtında bitir. Günün hər anı 0 və M arasında olan real bir ədədlə təmsil olunur, daxil olmaqla. Helen bütün mümkün fəaliyyətlərin siyahısını hazırlayıb, onların başlama və bitmə vaxtları ilə birlikdə. İndi o, hansı fəaliyyətlər alt qrupunu planlaşdıracağını qərarlaşdırmalıdır.
Əgər bir fəaliyyət S vaxtında başlayır və F vaxtında bitirsə, onda deyirik ki, bu fəaliyyət S və F arasında olan bütün anları əhatə edir, daxil olmaqla. Helen heç bir fəaliyyəti israf etmək istəmir, ona görə də günü əhatə edən minimal fəaliyyətlər alt qruplarını seçəcək. Bir fəaliyyətlər alt qrupu günü əhatə edən minimal alt qrupdur, əgər və yalnız əgər:
günün hər anı alt qrupun ən azı bir fəaliyyəti tərəfindən əhatə olunur; və
alt qrupdan hər hansı bir fəaliyyəti çıxarmaq günün ən azı bir anını əhatəsiz buraxar.
Qeyd edək ki, günün bəzi anları bir neçə fəaliyyət tərəfindən əhatə oluna bilər. Bir gün üçün mümkün fəaliyyətlərin siyahısı verildikdə, Helenə günü əhatə edən neçə fərqli minimal alt qrup olduğunu müəyyən etməyə kömək etməlisiniz.
Hər test halı bir neçə sətirdən istifadə edərək verilir. Birinci sətir günün bir anı üçün ən yüksək dəyəri (1 ≤ M ≤ 10^9) və gün üçün mümkün fəaliyyətlərin sayı (1 ≤ N ≤ 100) olan iki tam ədəd M və N ehtiva edir. Növbəti N sətirin hər biri bir mümkün fəaliyyəti təsvir edir və fəaliyyətin başlama və bitmə vaxtlarını təmsil edən iki tam ədəd S və F ehtiva edir (0 ≤ S < F ≤ M).
Son test halı iki sıfır ehtiva edən bir sətirlə izlənilir.
Hər test halı üçün günü əhatə edən minimal alt qrupların sayını təmsil edən tək bir tam ədəd çıxış edin. Həyatınızı asanlaşdırmaq üçün həllin 10^8 ilə bölünməsindən qalanı çap edin.
Nümunə 1