有一个 $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