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

Each cell is blocked or open. Water cannot pass through blocked cells. In each column, either no cells are blocked or all blocked cells form one consecutive block. Water cannot pass between adjacent blocked cells. A block containing a cell in the bottom row is called a floor-attached block; any other block is called a floating block.

Two blocks in adjacent columns merge into one if they contain cells in the same row. Water also cannot pass through their shared vertical boundary. This merging applies throughout consecutive columns. A floor-attached block and a floating block will never have to merge, as in columns two and three of the figure below: merging adjacent blocks are either both floor-attached or both floating. Also, two blocks will never meet at just one corner, as in columns five and six of the figure.

For example, the next figure shows an $8 \times 12$ grid. In the first column, cells in rows $6$ through $8$ are blocked; the second column has no blocked cells; and the third column has blocked cells in rows $5$ through $8$.

Suppose enough water is poured into this grid from above. Clearly, water collects in the cells marked $1$, and likewise those marked $2$. Water also collects in regions $3$ and $4$. This requires care: this problem assumes there is no air, so region $4$ fills to the same height as region $3$. (Equivalently, air may be thought of as passing through everything.) Region $5$ shows water collecting on top of a floating block. Note that water does not collect in cases like region $6$.

Write a program that reads the cell arrangement and prints the number of cells that retain water after enough water has been poured.

Input

Standard input gives the following information. The first line contains two integers $N,M$ ($1 \le N,M \le 100{,}000$). Each of the next $M$ lines contains two integers $A,B$ ($1 \le A \le B \le N$), describing columns from left to right: the blocked cells in that column occupy rows $A$ through $B$. As a special case, if a column has no blocked cells, both $A$ and $B$ are given as $0$.

Output

Print to standard output the number of cells in the given grid that retain water after enough water is poured.

Subtasks

• Subtask 1: $7$ of $100$ points. Blocked cells occur only in the first and last columns.
• Subtask 2: $18$ of $100$ points. If a column has blocked cells, its block is always attached to the floor.
• Subtask 3: $28$ of $100$ points. $1 \le N,M \le 1{,}000$.
• Subtask 4: $47$ of $100$ points. No constraints beyond the original ones.

Examples

Input 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

Output 1

22