ace

Pe o zonă în formă de dreptunghi cu laturile de lungimi $N$ și $M$ se găsesc $N \times M$ pătrate de latură $1$. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni $N$ și $M$, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului $(N,M)$ există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu $360\degree$ în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile.

De exemplu, dacă avem zona sub forma:

Din pătratul $(4,4)$, în direcția N (nord), camera va obține Fig. 1, iar în direcția V (vest) va obține Fig. 2.

Pentru direcția N, camera va vedea acul de coordonatele $(3,4)$ în totalitate, iar acul $(2,4)$ se va vedea doar parțial. Acul $(1,4)$ nu se vede pentru că este acoperit total de $(2,4)$.
În direcția V, camera va vedea doar acul $(4,3)$, deoarece $(4,2)$ și $(4,1)$ sunt acoperite total de $(4,3)$.
Pentru celelalte direcții se vor vedea parțial sau în totalitate acele $(3,3)$, $(3,2)$, $(3,1)$, $(2,3)$, $(1,3)$, $(2,2)$, $(2,1)$, $(1,2)$. Acul $(1,1)$ nu se vede din cauza acului $(2,2)$, care îl acoperă total. Acul $(2,2)$ se vede doar parțial, pentru că o parte din el este acoperit de acul $(3,3)$.

Cerinţe

1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?

Date de intrare

Fișierul de intrare ace.in conține pe prima linie numărul $P$ care poate fi $1$ sau $2$, pentru prima, respectiv a doua cerință.
Pe a doua linie se găsesc numerele $N$, $M$ reprezentând dimensiunile tabloului, apoi pe următoarele $N$ linii câte $M$ numere naturale, despărțite prin câte un spațiu, reprezentând înălțimile acelor.

Date de ieşire

Fișierul de ieșire ace.out va conține pe prima linie numărul de ace văzute pentru cerință indicată de valoarea numărului $P$.

Restricţii și precizări

• $2 \leq N \leq 1\ 000$
• $2 \leq M \leq 1\ 000$
• Elementele matricei sunt numere naturale nenule mai mici decât $1\ 000$, cu excepția numărului de pe linia $N$ și coloana $M$ care este $0$.
• Pentru rezolvarea corectă a cerinței 1 se acordă 20 de puncte, pentru rezolvarea corectă a cerinței 2 se acordă 70 de puncte, iar din oficiu se acordă 10 puncte.
• Pentru cerința 2 există teste în valoare de 20 de puncte cu $N,M \leq 50$.
• Pentru cerința 2 există teste în valoare de 45 de puncte cu $N,M \leq 100$.

Exemplul 1

ace.in

1
4 4
8 5 4 7
2 7 4 6
5 5 3 2
6 6 3 0

ace.out

3

Explicație

Pentru cerința 1 avem direcțiile N și V:

• Pentru direcția N, camera va vedea acul de coordonatele $(3,4)$ în totalitate, iar acul $(2,4)$ se va vedea doar parțial. Acul $(1,4)$ nu se va vedea pentru că este acoperit total de $(2,4)$.
• În direcția V, camera va vedea doar acul $(4,3)$, deoarece acele $(4,2)$ și $(4,1)$ sunt acoperite total de acul $(4,3)$.

Exemplul 2

ace.in

2
4 4
8 5 4 7
2 7 4 6
5 5 3 2
6 6 3 0

ace.out

11

Explicație

Pentru cerința 2 camera va vedea cele $3$ ace din direcțiile N și V (vezi mai sus) și $8$ pentru celelalte direcții se vor vedea parțial sau în totalitate acele $(3,3)$, $(3,2)$, $(3,1)$, $(2,3)$, $(1,3)$, $(2,2)$, $(2,1)$, $(1,2)$.

Acul $(1,1)$ nu se vede din cauza celui de pe $(2,2)$ care il acoperă total.
Acul $(2,2)$ se vede doar parțial, pentru că o parte din el este acoperit de acul $(3,3)$.

Exemplul 3

ace.in

2
4 3
5 4 7
6 4 6
5 3 2
6 3 0

ace.out

8

Explicație

Pentru cerința 2 camera va vedea în N acele $(3,3)$ și $(2,3)$, iar în V va vedea acul $(4,2)$. În celelalte direcții camera va vedea parțial sau în totalitate acele $(3,2)$, $(3,1)$, $(2,2)$, $(1,2)$, $(1,1)$.