Pe un lac de formă pătrată având latura de lungime N metri au crescut NxN nuferi, fiecare ocupând pe lac exact 1 metru pătrat. Lacul s-a împărţit astfel în N linii (numerotate de sus în jos de la 1 la N) şi N coloane (numerotate de la stânga la dreapta de la 1 la N). Pe unii dintre aceşti nuferi stau la soare K broscuţe, neexistând două broscuţe pe acelaşi nufăr. Atunci când două broscuţe doresc să comunice, se vor întâlni pe acelaşi nufăr. Dar orice broscuţă nu este dispusă să facă decât cel mult un salt pentru a ajunge pe un alt nufăr, iar saltul se face de pe nufărul unde se găseşte broscuţa pe un alt nufăr aflat pe aceeaşi diagonală. În imaginea de mai jos cu roşu este colorat nufărul pe care se află iniţial o broscuţă, iar cu verde sunt locurile posibile de salt ale broscuţei.
Dacă cele două broscuţe care doresc să comunice se află deja pe aceeaşi diagonală, atunci una din ele va sări direct pe nufărul celeilalte şi în acest caz există două locuri posibile de întâlnire. Dacă cele două broscuţe nu sunt pe aceeaşi diagonală, atunci, doar dacă este posibil, ambele vor face câte un salt pe un nufăr aflat la intersecţia a două diagonale şi în acest caz pot fi zero, unul sau două locuri de întâlnire posibile. De exemplu, dacă prima broscuţă se găseşte pe nufărul de la poziţia (5, 3) şi cealaltă la (6, 8), atunci fiecare va face un salt ca să ajungă fie la nufărul de la coordonatele (3, 5), fie la nufărul de la coordonatele (8, 6). În schimb, pentru două broscuţe aflate la coordonatele (2, 2) respectiv (1, 5) există un singur loc posibil de întâlnire, anume la poziţia (3, 3), iar pentru două broscuţe aflate la coordonatele (2, 2) respectiv (2, 5) nu există niciun loc de întâlnire.
Cerinţă
Scrieţi un program care să determine numărul locurilor posibile de întâlnire.
Date de intrare
Fişierul de intrare broscute.in
conţine pe prima linie numerele naturale N şi K separate printr-un spaţiu, iar pe următoarele K linii sunt câte două numere naturale x şi y reprezentând coordonatele unui nufăr pe care se află o broscuţă.
Date de ieşire
Fişierul de ieşire broscute.out
va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul locurilor posibile de întâlnire ale broscuţelor.
Restricţii
3 <= N <= 1000
2 <= K <= 200 000
Exemplu
broscute.in
broscute.out
Explicaţii
12 4
6 3
3 10
11 8
12 10
4
Pe lac se află 4 broscuţe. Există 4 posibile locuri de întâlnire:
- Nuferii de la poziţiile (6, 3) şi (11, 8), unde se pot întâlni broscuţele de la (6, 3) şi (11, 8), pentru că se află pe aceeaşi diagonală
- Nufărul de la poziţia (8, 5); acolo se pot întâlni broscuţele de la poziţiile (6, 3) şi (3, 10) sau se pot întâlni broscuţele de la poziţiile (3, 10) şi (11, 8)
- Nufărul de la poziţia (1, 8); acolo se pot întâlni broscuţele de la poziţiile (6, 3) şi (3, 10)
De remarcat că broscuţa de la (12, 10) nu se poate întâlni cu nicio altă broscuţă
