Problema número 738

Torfiles

Tiempo máximo: 1,000-4,000 sMemoria máxima: 16384 KiB
Movimiento de dos torfiles

En el juego del ajedrez hay distintos tipos de piezas cuyas reglas de movimiento varían. Por ejemplo la torre se mueve en horizontal o vertical, mientras que el alfil se mueve en ambas diagonales. Por su parte, la dama puede verse como la "suma" de alfil y torre, pues puede moverse tanto en horizontal y vertical como en cualquier diagonal.

Si entendemos la dama como la suma de alfil y torre, podemos inventarnos una figura nueva, el "torfil" que es mitad torre, mitad alfil: se mueve en horizontal pero no en vertical y en una diagonal pero no en las dos. En concreto, un torfil situado en la esquina inferior izquierda puede moverse por toda la fila inferior y por toda la diagonal hasta la esquina superior derecha.

Es curioso darse cuenta de que, en un tablero vacío, el número de posiciones a las que puede ir una figura como el torfil no siempre es el mismo. Por ejemplo si en lugar de situarlo en la esquina inferior izquierda lo situamos en la esquina inferior derecha su únicos destinos posibles serán la fila inferior.

Dado un tablero de N×N casillas con una serie de torfiles colocados en él, ¿cuántas casillas no son alcanzables por ninguna figura?

Entrada

La entrada estará compuesta por distintos casos de prueba, cada uno ocupando varias líneas.

La primera línea de cada caso contiene dos números: el número N que representa el tamaño del tablero, que siempre es cuadrado (1 ≤ N ≤ 300.000) y el número P de torfiles que hay sobre él (0 ≤ P ≤ min(4×N,N×N)).

A continuación aparecerán P líneas con las coordenadas de cada uno de los torfiles. El primer número representará la fila y el segundo la columna (la coordenada 1 1 representa la esquina inferior izquierda).

Salida

Por cada caso de prueba se escribirá un único número con la cantidad de casillas del tablero que no son alcanzables, en un solo movimiento, por ningún torfil. Las casillas ocupadas por torfiles al principio se consideran alcanzables.

Entrada de ejemplo

8 2
7 3
3 3
4 0
300000 0

Salida de ejemplo

39
16
90000000000