有一個 $N \times M$ 的網格，左上角的格子為 $(1,1)$，右下角的格子為 $(N,M)$。最底下一列的正下方有一層水無法穿透的地板。

每個格子要麼被阻塞，要麼暢通，水無法穿過被阻塞的格子。每一直行要麼沒有阻塞格，要麼所有阻塞格連續形成一個塊。水無法從相鄰阻塞格之間穿過。如果一直行中的塊包含最底下一列的格子，就稱為貼地塊；否則稱為懸空塊。

相鄰兩直行的兩個塊如果包含同一橫列的格子，就會連接成一個塊。水也無法穿過它們連接處的垂直邊界。這種連接適用於所有連續的直行。保證不會出現下圖第 $2$、$3$ 直行那樣、貼地塊與懸空塊需要連接的情況，即相鄰直行中連接的塊要麼都貼地，要麼都懸空。也不會出現下圖第 $5$、$6$ 直行那樣、兩個塊僅在一個角點相接的情況。

例如，下圖是一個 $8 \times 12$ 的網格。第一直行的第 $6$ 至 $8$ 橫列被阻塞，第二直行沒有阻塞格，第三直行的第 $5$ 至 $8$ 橫列被阻塞。

假設從上方向該網格倒入足夠多的水。顯然，標為 $1$ 的格子會積水，標為 $2$ 的格子也一樣。標為 $3$、$4$ 的格子也會積水。這一點需要注意：本題認為不存在空氣，因此區域 $4$ 會積水到與區域 $3$ 相同的高度。（也可以認為空氣能穿過一切。）區域 $5$ 展示了懸空塊上方積水的情況。注意，區域 $6$ 這樣的情況不會積水。

編寫程式，讀入格子的布局，輸出倒入足夠多的水後會積水的格子數量。

輸入格式

標準輸入給出以下資訊。第一列給出兩個整數 $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