Hay una cuadrícula de $N \times M$. La celda superior izquierda es $(1,1)$ y la inferior derecha es $(N,M)$. Justo debajo de la última fila hay un suelo impermeable.

Cada celda está bloqueada o abierta. El agua no atraviesa las celdas bloqueadas. En cada columna no hay celdas bloqueadas o todas forman un único bloque consecutivo. El agua no pasa entre celdas bloqueadas adyacentes. Un bloque que incluye una celda de la última fila se llama apoyado en el suelo; cualquier otro se llama flotante.

Dos bloques de columnas adyacentes se unen si contienen celdas en la misma fila. El agua tampoco atraviesa su frontera vertical compartida. Esta unión se aplica a todas las columnas consecutivas. Nunca habrá que unir un bloque apoyado con uno flotante, como en las columnas segunda y tercera de la figura: los bloques que se unen están ambos apoyados o ambos flotantes. Tampoco habrá bloques que se toquen solo en un vértice, como en las columnas quinta y sexta.

Por ejemplo, la siguiente figura muestra una cuadrícula de $8 \times 12$. En la primera columna están bloqueadas las filas de $6$ a $8$; en la segunda no hay celdas bloqueadas; y en la tercera están bloqueadas las filas de $5$ a $8$.

Supón que se vierte suficiente agua desde arriba. Se acumula en las celdas marcadas $1$ y también en las marcadas $2$. También se acumula en las regiones $3$ y $4$. Ten cuidado: se supone que no hay aire, por lo que la región $4$ se llena hasta la misma altura que la $3$. (También se puede suponer que el aire atraviesa todo.) La región $5$ muestra agua sobre un bloque flotante. Observa que el agua no se acumula en casos como la región $6$.

Escribe un programa que lea la disposición de las celdas e imprima cuántas retienen agua tras verter una cantidad suficiente.

Entrada

La entrada estándar tiene el siguiente formato. La primera línea contiene dos enteros $N,M$ ($1 \le N,M \le 100{,}000$). Cada una de las siguientes $M$ líneas contiene dos enteros $A,B$ ($1 \le A \le B \le N$), describiendo las columnas de izquierda a derecha: las celdas bloqueadas ocupan las filas de $A$ a $B$. En el caso especial de una columna sin celdas bloqueadas, tanto $A$ como $B$ son $0$.

Salida

Imprime en la salida estándar la cantidad de celdas de la cuadrícula que retienen agua tras verter suficiente agua.

Subtareas

• Subtarea 1: $7$ de $100$ puntos. Solo hay celdas bloqueadas en la primera y la última columna.
• Subtarea 2: $18$ de $100$ puntos. Si una columna tiene celdas bloqueadas, su bloque está apoyado en el suelo.
• Subtarea 3: $28$ de $100$ puntos. $1 \le N,M \le 1{,}000$.
• Subtarea 4: $47$ de $100$ puntos. No hay restricciones adicionales.

Ejemplos

Entrada 1

8 12
6 8
0 0
5 8
7 8
5 8
0 0
1 6
2 2
1 6
0 0
5 8
0 0

Salida 1

22