magnify

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

Pradiniai duomenys Rezultatai Paaiškinimas
5
6
1 2
1 3
2 1
3 5
4 2
5 4
3
Tai pavyzdys iš iliustracijos. Voverė gali pagauti tris giles keliais skirtingais būdais, tačiau negali spėti pagauti keturių ar daugiau gilių. Vienas iš būdų pagauti tris giles: pirmuoju laiko momentu pagauti gilę trečiojoje pozicijoje, trečiu laiko momentu – penktojoje pozicijoje (Alfa gali spėti peršokti į penktąją poziciją iš trečiosios per du laiko vienetus), ir penktuoju laiko momentu – ketvirtojoje pozicijoje.
7
7
1 3
2 2
3 5
4 5
4 7
5 4
5 7
4
Pirmuoju laiko momentu Alfa iš ketvirtosios (vidurinės) pozicijos gali peršokti į trečiąją (ir pagauti gilę!), pagauti abi giles penktojoje pozicijoje (trečiuoju ir ketvirtuoju laiko momentais), o penktuoju – pagauti gilę ketvirtojoje pozicijoje.
© Bronė Narkevičienė