Ferkovi sa sníval hrozne zvláštny sen. Vo sne šoféroval po hrboľatej diaľnici. Za oknami sa mihala ubiehajúca krajina a Ferko uháňal na plný plyn. Potom zrazu niekde zastal, vytiahol lopatu a začal rovno pri ceste kopať. Za chvíľu vykopal truhlicu a v nej bol obrovský zlatý poklad.

Keď sa Ferko zobudil, bolo mu jasné že ten sen musí byť prorocká vízia. Vytiahol atlas, našiel v ňom najbližšiu diaľnicu a pustil sa hľadať, kde by ten poklad mohol byť. Ale ako to pri snoch bohužiaľ býva, všetky detaily okamžite zabudol a zostali mu v pamäti len hmlisté obrysy.

Pomôžte Ferkovi spomenúť si, kde má kopať!

Úloha

Mapa hrboľatej diaľnice je rozdelená na $n$ kilometrov. O každom kilometri mapa hovorí, aký je strmý, čiže o koľko metrov stúpne alebo klesne naša nadmorská výška ak ním prejdeme. Tiež o každom kilometri vieme, či tam diaľnica vedie cez les alebo cez pole.

Ferko vo sne prešiel nejaký súvislý úsek diaľnice. Ale vôbec si nevie spomenúť, koľko kilometrov dokopy prešiel, na akom mieste začal, ani kde skončil. Pamätá si iba zopár vecí:

• Išiel smerom preč od svojho mesta (nie v protismere).

• Začiatok aj koniec boli pri nejakom diaľničnom stĺpiku, čiže na celočíselnej pozícii.

• Na začiatku sna išiel presne jeden kilometer cez les. Odvtedy už nikdy znova nešiel cez les.

• Na konci cesty bola Ferkova nadmorská výška presne o $s$ metrov vyššie, ako na začiatku. (Ak je $s$ záporné, skončil nižšie.)

To ešte stále nemusí byť jednoznačné. Preto spočítajte počet možností, kde sa mohol sen odohrať.

Dve možnosti považujeme za rôzne, ak začínajú alebo končia na inom mieste.

Formát vstupu

Na prvom riadku je celé číslo $s$ udávajúce, o koľko dokopy stúpla/klesla Ferkova nadmorská výška počas jeho vysnívanej cesty.

Na druhom riadku je kladné celé číslo $n$ udávajúce celkovú dĺžku diaľnice v kilometroch.

Ďalej nasleduje $n$ riadkov obsahujúcich dve celé čísla $v_i$ a $k_i$. $v_i$ určuje zmenu nadmorskej výšky na $i$-tom kilometri. $k_i$ sa rovná buď $1$ ak je na $i$-tom kilometri les, alebo $0$ ak je tam pole.

V jednotlivých sadách platia nasledujúce obmedzenia:

Ak programujete v jazyku C++, dajte si pozor na veľkosť číselných premenných. Použite radšej long long ako int.

Formát výstupu

Vypíšte jedno nezáporné celé číslo: počet rôznych úsekov diaľnice, ktoré sa mohli Ferkovi snívať.

Príklady

Input:

9
10
1 0
8 0
4 1
5 0
7 1
1 0
20 1
-11 0
0 0
2 0

Output:

3

Vo sne mohol prejsť tretí a štvrtý kilometer ($4+5=9$), alebo siedmy a ôsmy kilometer ($20-11=9$), alebo siedmy až deviaty kilometer ($20-11+0=9$).

Input:

5
8
2 1
3 0
4 0
0 0
-4 0
0 0
3 1
5 1

Output:

4

Možnosti sú $2+3=5$, $2+3+4+0-4=5$, $2+3+4+0-4+0=5$ alebo $5=5$.

Input:

0
3
0 0
0 0
0 0

Output:

0

Diaľnica vedie po rovine, čo by síce sedelo, ale ide iba cez polia – les nikde. Predsalen to nebol prorocký sen.