==Include(page="template/taskheader" task_id="zc")==
Zota si Chidil s-au certat. De aceasta data, Zota, dorind sa se razbune, planuieste sa insire o serie de capcane in padurea prin care Chidil obisnuieste sa se plimbe. Astfel, folosind o formula magica, el asterne o capcana in mai multe celule ale padurii. Toate celulele care se afla la o distanta Manhattan mai mica sau egala cu _2_ de capcana sunt si ele afectatate.

In imaginea de mai jos capcana este reprezentata prin **O** iar celelalte celule afectate sunt marcate cu **X**.

In imaginea de mai jos capcana este reprezentata prin $O$ iar celelalte celule afectate sunt marcate cu $X$.

     $.......$
     $...X...$
     $..XXX..$
     $.XXOXX.$
     $..XXX..$
     $...X...$
     $.......$

$.......$
$...X...$
$..XXX..$
$.XXOXX.$
$..XXX..$
$...X...$
$.......$

Chidil isi planifica intotdeauna traseul. El porneste intotdeauna din celula cu coordonate (0, 0). Drumul lui este descris printr-o pereche ({$D$}, {$x$}) unde D apartine multimii {**N**, **E**, **S**, **V**}, iar $x$ este un numar natural nenul. Aceasta inseamna ca din pozitia in care se afla, va face $x$ pasi in directia $D$.

Chidil isi planifica intotdeauna traseul. El porneste intotdeauna din celula cu coordonate (0, 0). Drumul lui este descris printr-o pereche ({$D$}, {$x$}) unde D apartine multimii {$N$, $E$, $S$, $V$}, iar $x$ este un numar natural nenul. Aceasta inseamna ca din pozitia in care se afla, va face $x$ pasi in directia $D$.

Desi afla de planul malefic al lui Zota, Chidil nu vrea sa isi schimbe traseul cu nici un chip. Prefera sa afle cate celule din traseul lui contin capcane sau sunt afectate de capcane, pentru a sti exact cat praf magic pentru neutralizarea celulelor sa ia la el.
h2. Cerinta

h2. Date de intrare

Linia 1 a fisierului de intrare se afla doua numere naturale $N$ si $M$, reprezentand numarul de capcane intinse de Zota, respectiv numarul de perechi ({$D$}, $x$)conform carora Chidil urmeaza sa se deplaseze.

Pe prima linie a fisierului de intrare $zc.in$ se afla doua numere naturale $N$ si $M$, reprezentand numarul de capcane intinse de Zota, respectiv numarul de perechi ({$D$}, $x$) conform carora Chidil urmeaza sa se deplaseze.

Liniile $2 .. N+1$ contin cate o pereche de numere ({$x$} {$y$}), ce reprezinta coordonatele capcanelor.

h2. Date de iesire

Fisierul de iesire va contine pe prima linie numarul de celule periculoase care trebuie neutralizate de Chidil in drumul sau.

Fisierul de iesire $zc.out$ va contine pe prima linie numarul de celule periculoase care trebuie neutralizate de Chidil in drumul sau.

h2. Restrictii si precizari
* $1 ≤ N, M ≤ 100 000$
* Coordonatele lui Chidil nu vor iesi niciodata din intervalul [$-2 000 000 000$, $2 000 000 000$]

* chiar daca celula de pornire a lui Chidil contine sau este afectata de o capcana, nu este nevoie de praf magic pentru a o neutraliza
* desi o celula poate fi afectata de mai multe capcane, este nevoie de o singura unitate de praf magic pentru a o neutraliza
* efectul prafului magic este temporar; de fiecare data cand Chidil trece printr-o celula afectata, are nevoie de praf magic pt a o neutraliza

* Chiar daca celula de pornire a lui Chidil contine sau este afectata de o capcana, nu este nevoie de praf magic pentru a o neutraliza
* Desi o celula poate fi afectata de mai multe capcane, este nevoie de o singura unitate de praf magic pentru a o neutraliza
* Efectul prafului magic este temporar; de fiecare data cand Chidil trece printr-o celula afectata, are nevoie de praf magic pt a o neutraliza

h2. Exemplu

table(example). |_. zc.in |_. zc.out |_. Explicatii |

table(example). |_. zc.in |_. zc.out |

| 2 8
5 6
12 10

E 6
N 6
V 3

| 4
| ...........####............
............X.#............
...........XXX#............
......###.XXOX#............
......#.#..XXX#............
.....X#.#...X.#............
....XX#.#######.............
...XXO#X...................
....XX#....................
.....X#....................
#######....................
#..........................
#..........................
#.......................... |

| 4 |
 
h3. Explicatii
 
$...........####............$
$............X.#............$
$...........XXX#............$
$......###.XXOX{%{color:red}#%}............$
$......#.#..XXX#............$
$.....X#.#...X.#............$
$....XX{%{color:red}#%}.#######............$
$...XXO{%{color:red}#%}X...................$
$....XX{%{color:red}#%}....................$
$.....X#....................$
$#######....................$
$#..........................$
$#..........................$
$#..........................$

==Include(page="template/taskfooter" task_id="zc")==

729