$N \times M$ のマス目があり、左上のマスを $(1,1)$、右下を $(N,M)$ とする。最下行のすぐ下には水を通さない床がある。

各マスは塞がれているか開いている。塞がれたマスは水を通さない。各列には塞がれたマスがないか、連続した一つの塊がある。隣接する塞がれたマスの間も水は通らない。最下行のマスを含む列の塊を床に接する塊、それ以外を浮いた塊と呼ぶ。

隣接する列の二つの塊が同じ行のマスを含むなら、つながって一つの塊になる。その縦の接合境界も水は通らない。この結合は連続するすべての列に適用される。下図の2列目と3列目のように、床に接する塊と浮いた塊が結合する場合は与えられない。つまり、結合する隣接列の塊は両方とも床に接するか、両方とも浮いている。また、下図の5列目と6列目のように一つの頂点だけで接する塊も与えられない。

例えば次の図は $8 \times 12$ のマス目である。1列目は $6$ 行目から $8$ 行目が塞がれ、2列目には塞がれたマスがなく、3列目は $5$ 行目から $8$ 行目が塞がれている。

このマス目に上から十分な水を注いだとする。$1$ のマスに水がたまることは明らかで、$2$ も同様である。$3$ と $4$ にも水がたまる。ここは注意が必要で、本問では空気がないと考えるため、$4$ にも $3$ と同じ高さまで水がたまる。（空気はすべてを通り抜けると考えても同じである。）$5$ は浮いた塊の上に水がたまる例である。$6$ のような場所には水がたまらないことに注意せよ。

マスの配置を読み込み、十分な水を注いだときに水がたまるマスの個数を出力するプログラムを作成せよ。

入力

標準入力は次の形式である。1行目に整数 $N,M$（$1 \le N,M \le 100{,}000$）が与えられる。続く $M$ 行には各々整数 $A,B$（$1 \le A \le B \le N$）が与えられ、左から順に各列の $A$ 行目から $B$ 行目が塞がれていることを表す。特別に、塞がれたマスがない列では $A,B$ はともに $0$ である。

出力

与えられたマス目に十分な水を注いだときに水がたまるマスの個数を標準出力に出力せよ。

小課題

• 小課題 1：$100$ 点中 $7$ 点。塞がれたマスは最初と最後の列にしかない。
• 小課題 2：$100$ 点中 $18$ 点。塞がれたマスのある列では、その塊は必ず床に接している。
• 小課題 3：$100$ 点中 $28$ 点。$1 \le N,M \le 1{,}000$。
• 小課題 4：$100$ 点中 $47$ 点。元の制約以外に追加制約はない。

入出力例

入力 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

出力 1

22