Mamy siatkę $N \times M$. Lewa górna komórka to $(1,1)$, a prawa dolna to $(N,M)$. Bezpośrednio pod dolnym wierszem znajduje się nieprzepuszczalna dla wody podłoga.

Każda komórka jest zablokowana lub otwarta. Zablokowane komórki nie przepuszczają wody. W każdej kolumnie albo ich nie ma, albo tworzą jeden spójny pionowy blok. Woda nie przepływa między sąsiednimi zablokowanymi komórkami. Blok zawierający komórkę dolnego wiersza nazywamy opartym na podłodze, a każdy inny — wiszącym.

Dwa bloki w sąsiednich kolumnach łączą się, jeśli zawierają komórki w tym samym wierszu. Woda nie przenika też przez ich wspólną pionową granicę. Łączenie dotyczy wszystkich kolejnych kolumn. Nie wystąpi sytuacja wymagająca połączenia bloku opartego na podłodze z wiszącym, jak w kolumnach drugiej i trzeciej na rysunku: łączone bloki są albo oba oparte, albo oba wiszące. Nie wystąpi też zetknięcie bloków tylko w jednym narożniku, jak w kolumnach piątej i szóstej.

Na przykład następny rysunek pokazuje siatkę $8 \times 12$. W pierwszej kolumnie zablokowane są wiersze od $6$ do $8$, druga nie ma zablokowanych komórek, a w trzeciej zablokowane są wiersze od $5$ do $8$.

Załóżmy, że z góry wlano dostatecznie dużo wody. Woda zbierze się w komórkach oznaczonych $1$, podobnie w tych oznaczonych $2$. Zbierze się też w obszarach $3$ i $4$. Uwaga: w tym zadaniu zakładamy brak powietrza, więc obszar $4$ wypełni się do tej samej wysokości co $3$. (Równoważnie można uznać, że powietrze przenika przez wszystko.) Obszar $5$ pokazuje wodę na wiszącym bloku. W miejscach takich jak obszar $6$ woda się nie zatrzymuje.

Napisz program odczytujący układ komórek i wypisujący liczbę komórek zatrzymujących wodę po wlaniu jej dostatecznej ilości.

Wejście

Standardowe wejście ma następującą postać. Pierwszy wiersz zawiera dwie liczby całkowite $N,M$ ($1 \le N,M \le 100{,}000$). Kolejne $M$ wierszy zawiera po dwie liczby całkowite $A,B$ ($1 \le A \le B \le N$), opisujące kolumny od lewej do prawej: zablokowane są wiersze od $A$ do $B$. Wyjątkowo, jeśli kolumna nie ma zablokowanych komórek, zarówno $A$, jak i $B$ wynoszą $0$.

Wyjście

Wypisz na standardowe wyjście liczbę komórek siatki zatrzymujących wodę po wlaniu jej dostatecznej ilości.

Podzadania

• Podzadanie 1: $7$ ze $100$ punktów. Zablokowane komórki występują tylko w pierwszej i ostatniej kolumnie.
• Podzadanie 2: $18$ ze $100$ punktów. Jeśli kolumna ma zablokowane komórki, jej blok jest oparty na podłodze.
• Podzadanie 3: $28$ ze $100$ punktów. $1 \le N,M \le 1{,}000$.
• Podzadanie 4: $47$ ze $100$ punktów. Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

22