小爱丽丝在生日时收到了一张现代像素画。

这张画是一个大小为 $n \times m$ 的矩形网格。网格的每一列都有一个或多个连续的黑色单元格，其余单元格均为白色。

如果任意两个黑色单元格 $u$ 和 $v$ 之间都存在一条仅由黑色单元格组成的路径（即从黑色单元格 $u$ 出发，移动到相邻的黑色单元格 $w$，再移动到与 $w$ 相邻的黑色单元格，以此类推，最终到达黑色单元格 $v$），爱丽丝就认为这张画是“美丽的”。

由于这张画是现代风格的，它可以被修改。在一次操作中，你可以选择任意一列，并将该列中所有的黑色单元格向同一个方向（向上或向下）移动一个单元格。只有当移动后的单元格仍在网格范围内时，才能进行移动。

爱丽丝想知道，要使这张画变得“美丽”，最少需要进行多少次操作。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示画的行数和列数（$1 \le n, m \le 100\,000$）。保证网格单元格的总数不超过 $10^6$（$1 \le n \cdot m \le 1\,000\,000$）。

接下来的 $m$ 行，每行包含两个整数 $s_i$ 和 $t_i$，表示第 $i$ 列中黑色单元格的起始和结束位置（$1 \le s_i \le t_i \le n$）。

输出格式

输出一个整数，表示使给定的画变得“美丽”所需的最少操作次数。

样例

输入 1

9 3
1 2
4 5
7 9

输出 1

4