Es gibt ein Raster mit $N \times M$ Zellen. Die linke obere Zelle ist $(1,1)$, die rechte untere $(N,M)$. Direkt unter der untersten Zeile liegt ein wasserundurchlässiger Boden.

Jede Zelle ist blockiert oder offen. Blockierte Zellen lassen kein Wasser durch. Jede Spalte enthält entweder keine blockierten Zellen oder genau einen zusammenhängenden Block davon. Zwischen benachbarten blockierten Zellen kann kein Wasser hindurch. Ein Block, der eine Zelle der untersten Zeile enthält, heißt am Boden anliegend; jeder andere heißt schwebend.

Zwei Blöcke benachbarter Spalten verbinden sich, wenn sie Zellen derselben Zeile enthalten. Auch durch ihre gemeinsame senkrechte Grenze kann kein Wasser dringen. Dies gilt für alle aufeinanderfolgenden Spalten. Ein anliegender und ein schwebender Block müssen niemals verbunden werden, wie in der zweiten und dritten Spalte der Abbildung: Verbundene Blöcke sind entweder beide anliegend oder beide schwebend. Auch berühren sich niemals zwei Blöcke nur in einem Eckpunkt, wie in der fünften und sechsten Spalte.

Die nächste Abbildung zeigt beispielsweise ein Raster mit $8 \times 12$ Zellen. In der ersten Spalte sind die Zeilen $6$ bis $8$ blockiert, in der zweiten keine Zellen und in der dritten die Zeilen $5$ bis $8$.

Es werde genügend Wasser von oben hineingegossen. In den mit $1$ markierten Zellen sammelt sich Wasser, ebenso in denen mit $2$. Auch in den Bereichen $3$ und $4$ sammelt es sich. Hier ist Vorsicht nötig: Da es in dieser Aufgabe keine Luft gibt, füllt sich Bereich $4$ bis zur gleichen Höhe wie Bereich $3$. (Man kann gleichwertig annehmen, dass Luft alles durchdringt.) Bereich $5$ zeigt Wasser auf einem schwebenden Block. Beachte, dass sich in Fällen wie Bereich $6$ kein Wasser sammelt.

Schreibe ein Programm, das die Zellanordnung einliest und die Anzahl der Zellen ausgibt, in denen nach genügend Wasserzugabe Wasser zurückbleibt.

Eingabe

Die Standardeingabe hat folgendes Format. Die erste Zeile enthält zwei ganze Zahlen $N,M$ ($1 \le N,M \le 100{,}000$). Jede der nächsten $M$ Zeilen enthält zwei ganze Zahlen $A,B$ ($1 \le A \le B \le N$) und beschreibt eine Spalte von links nach rechts: Die Zeilen $A$ bis $B$ sind blockiert. Hat eine Spalte keine blockierten Zellen, werden als Sonderfall sowohl $A$ als auch $B$ mit $0$ angegeben.

Ausgabe

Gib auf der Standardausgabe die Anzahl der Zellen des Rasters aus, in denen nach genügend Wasserzugabe Wasser zurückbleibt.

Teilaufgaben

• Teilaufgabe 1: $7$ von $100$ Punkten. Nur die erste und letzte Spalte enthalten blockierte Zellen.
• Teilaufgabe 2: $18$ von $100$ Punkten. Hat eine Spalte blockierte Zellen, liegt ihr Block am Boden an.
• Teilaufgabe 3: $28$ von $100$ Punkten. $1 \le N,M \le 1{,}000$.
• Teilaufgabe 4: $47$ von $100$ Punkten. Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 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

Ausgabe 1

22