Water Filling

There is an $N \times M$ grid of cells. Call the top-left cell $(1, 1)$ and the bottom-right cell $(N, M)$. Directly below the bottom row is a floor that water cannot pass through.

Each cell is either blocked or open. Water cannot pass through a blocked cell. In each column, the blocked cells are either absent or form one contiguous block. Water also cannot pass between two adjacent blocked cells. A block in a column that includes a cell in the bottom row is called a block resting on the floor. A block that does not touch the floor is called a floating block.

When two blocks in adjacent columns contain a cell in the same row, the two blocks join into one block. Water cannot pass through the vertical boundary where they join. This joining applies to every pair of consecutive columns. The case in the figure where a block resting on the floor joins with a floating block, as in the second and third columns, is not given. In other words, blocks in adjacent columns join only when both rest on the floor or both float. The case where two blocks meet at only one corner, as in the fifth and sixth columns of the figure, is also not given.

For example, the figure below shows an $8 \times 12$ grid. The first column is blocked from the 6th cell to the 8th cell, the second column has no blocked cells, and the third column is blocked from the 5th cell to the 8th cell.

Suppose enough water is poured in from the top. Water clearly pools in the cells marked 1, and in the cells marked 2. Water also pools in the cells marked 3 and 4. This part needs care. The problem assumes there is no air, so the cells marked 4 fill up to the same height as the cells marked 3. (The result is the same if you assume air passes through everything.) The cells marked 5 are where water pools on top of a floating block. Water does not pool in the situation shown by the cells marked 6.

Given the layout of the cells, write a program that prints the number of cells where water pools after enough water is poured in.

The first line contains two integers $N$ and $M$. ($1 \le N, M \le 100,000$) The next $M$ lines each contain two integers $A$ and $B$. ($1 \le A \le B \le N$) From left to right, these give the rows $A$ through $B$ where the blocked cells are in the corresponding column. If a column has no blocked cells, both $A$ and $B$ are given as 0.

Print the number of cells where water pools after enough water is poured onto the given grid.