Há uma grade de $N \times M$. A célula superior esquerda é $(1,1)$ e a inferior direita é $(N,M)$. Logo abaixo da última linha há um piso impermeável.

Cada célula é bloqueada ou aberta. A água não atravessa células bloqueadas. Em cada coluna, ou não há células bloqueadas, ou todas formam um único bloco consecutivo. A água não passa entre células bloqueadas adjacentes. Um bloco que inclui uma célula da última linha é chamado de apoiado no piso; qualquer outro é chamado de flutuante.

Dois blocos em colunas adjacentes se unem se contiverem células na mesma linha. A água também não atravessa sua fronteira vertical compartilhada. Essa união se aplica a todas as colunas consecutivas. Nunca será necessário unir um bloco apoiado a um flutuante, como nas colunas segunda e terceira da figura: os blocos que se unem são ambos apoiados ou ambos flutuantes. Também não haverá blocos que se toquem apenas em um vértice, como nas colunas quinta e sexta.

Por exemplo, a figura seguinte mostra uma grade de $8 \times 12$. Na primeira coluna, as linhas de $6$ a $8$ estão bloqueadas; na segunda, não há células bloqueadas; e na terceira, as linhas de $5$ a $8$ estão bloqueadas.

Suponha que água suficiente seja despejada de cima. Ela se acumula nas células marcadas $1$, assim como nas marcadas $2$. Também se acumula nas regiões $3$ e $4$. Atenção: neste problema não há ar, portanto a região $4$ se enche até a mesma altura da região $3$. (É equivalente supor que o ar atravessa tudo.) A região $5$ mostra água sobre um bloco flutuante. Observe que a água não se acumula em casos como a região $6$.

Escreva um programa que leia a disposição das células e imprima quantas retêm água após despejar uma quantidade suficiente.

Entrada

A entrada padrão tem o seguinte formato. A primeira linha contém dois inteiros $N,M$ ($1 \le N,M \le 100{,}000$). Cada uma das próximas $M$ linhas contém dois inteiros $A,B$ ($1 \le A \le B \le N$), descrevendo as colunas da esquerda para a direita: as células bloqueadas ocupam as linhas de $A$ a $B$. No caso especial de uma coluna sem células bloqueadas, tanto $A$ quanto $B$ são $0$.

Saída

Imprima na saída padrão a quantidade de células da grade que retêm água após despejar água suficiente.

Subtarefas

• Subtarefa 1: $7$ de $100$ pontos. Só há células bloqueadas na primeira e na última coluna.
• Subtarefa 2: $18$ de $100$ pontos. Se uma coluna tem células bloqueadas, seu bloco é apoiado no piso.
• Subtarefa 3: $28$ de $100$ pontos. $1 \le N,M \le 1{,}000$.
• Subtarefa 4: $47$ de $100$ pontos. Não há restrições adicionais.

Exemplos

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

Saída 1

22