On dispose d’une grille de $N \times M$ cases. La case supérieure gauche est $(1,1)$ et la case inférieure droite est $(N,M)$. Juste sous la dernière ligne se trouve un sol imperméable.

Chaque case est bloquée ou ouverte. L’eau ne traverse pas les cases bloquées. Chaque colonne ne contient aucune case bloquée ou contient un seul bloc de cases bloquées consécutives. L’eau ne passe pas entre deux cases bloquées adjacentes. Un bloc contenant une case de la dernière ligne est dit posé sur le sol ; tout autre bloc est dit flottant.

Deux blocs de colonnes voisines fusionnent s’ils contiennent des cases de la même ligne. L’eau ne traverse pas non plus leur frontière verticale commune. Cette fusion s’applique à toutes les colonnes consécutives. On n’aura jamais à fusionner un bloc posé et un bloc flottant, comme dans les deuxième et troisième colonnes de la figure : les blocs fusionnés sont tous deux posés ou tous deux flottants. Deux blocs ne se toucheront jamais non plus par un seul sommet, comme dans les cinquième et sixième colonnes.

La figure suivante montre par exemple une grille de $8 \times 12$ cases. Dans la première colonne, les lignes $6$ à $8$ sont bloquées ; la deuxième n’a aucune case bloquée ; dans la troisième, les lignes $5$ à $8$ sont bloquées.

Supposons que l’on verse suffisamment d’eau par le haut. L’eau s’accumule dans les cases marquées $1$, de même que dans celles marquées $2$. Elle s’accumule aussi dans les régions $3$ et $4$. Attention : on suppose ici qu’il n’y a pas d’air, donc la région $4$ se remplit à la même hauteur que la région $3$. (On peut aussi considérer que l’air traverse tout.) La région $5$ montre de l’eau accumulée sur un bloc flottant. Remarquez que l’eau ne s’accumule pas dans des cas comme la région $6$.

Écrivez un programme qui lit la disposition des cases et affiche combien retiennent de l’eau après en avoir versé suffisamment.

Entrée

L’entrée standard a le format suivant. La première ligne contient deux entiers $N,M$ ($1 \le N,M \le 100{,}000$). Chacune des $M$ lignes suivantes contient deux entiers $A,B$ ($1 \le A \le B \le N$), décrivant les colonnes de gauche à droite : les cases bloquées occupent les lignes $A$ à $B$. Dans le cas particulier d’une colonne sans case bloquée, $A$ et $B$ valent tous deux $0$.

Sortie

Affichez sur la sortie standard le nombre de cases de la grille qui retiennent de l’eau après en avoir versé suffisamment.

Sous-tâches

• Sous-tâche 1 : $7$ points sur $100$. Seules la première et la dernière colonne contiennent des cases bloquées.
• Sous-tâche 2 : $18$ points sur $100$. Si une colonne contient des cases bloquées, son bloc est posé sur le sol.
• Sous-tâche 3 : $28$ points sur $100$. $1 \le N,M \le 1{,}000$.
• Sous-tâche 4 : $47$ points sur $100$. Aucune contrainte supplémentaire.

Exemples

Entrée 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

Sortie 1

22