Gilės

Pradinių duomenų failas:

giles.in  

Rezultatų failas:

giles.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Artėjant žiemai labai svarbu sukaupti pakankamai maisto atsargų. Tai supranta net tingiausia iš visų voverė (sciurus vulgaris) Alfa. Negaišdama laiko maisto rinkimui, Alfa susisuko savo gūžtą ąžuolo šakose. Vėjuotą dieną, nušokavusi iki didelės ir patogios šakos, ji gaudo žemyn krintančias giles.

Ant Alfos mėgstamiausios šakos yra P patogių pozicijų, kuriose ji gali tupėti. Per vieną laiko vienetą ji gali peršokti į gretimą poziciją kairėje ar dešinėje, arba likti toje pačioje pozicijoje. Jei kažkuriuo laiko momentu, Alfai tupint (arba nutupiant) pozicijoje p, į šią vietą krinta gilė, voverė ją pagauna.

Pradiniu (nuliniu) laiko momentu voverė tupi vidurinėje pozicijoje. Ar galite suskaičiuoti, kiek daugiausiai gilių gali spėti pagauti Alfa, jei žinoma, kur kiekvienu laiko momentu kris gilės? Parašykite programą, sprendžiančią šį uždavinį.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas nelyginis skaičius P – pozicijų skaičius (1 <= P <= 15, kadangi P yra nelyginis skaičius, viduriniosios pozicijos numeris yra (P + 1) / 2). Antroje – gilių skaičius N (0 <= N <= 50000). Tolesnėse N eilučių įrašytos sveikųjų skaičių \(t_{k}\) ir \(p_{k}\) poros (1 <= \(t_{k}\) <= 10000, 1 <= \(p_{k}\) <= P), reiškiančių, jog k-toji gilė laiko momentu \(t_{k}\) nukris pozicijoje \(p_{k}\). Skaičių poros pateiktos laiko momentų (\(t_{k}\)) didėjimo tvarka.

Rezultatai

Pirmoje ir vienintelėje rezultatų failo eilutėje turi būti įrašytas sveikas skaičius M – didžiausias gilių, kurias gali suspėti pagauti Alfa, skaičius.

Pavyzdžiai

5
6
1 2
1 3
2 1
3 5
4 2
5 4

3

7
7
1 3
2 2
3 5
4 5
4 7
5 4
5 7

4