CF354D.Transferring Pyramid

Vasya and Petya are using an interesting data storing structure: a pyramid.

The pyramid consists of n rows, the i-th row contains i cells. Each row is shifted half a cell to the left relative to the previous row. The cells are numbered by integers from 1 to as shown on the picture below.

An example of a pyramid at n = 5 is:

This data structure can perform operations of two types:

1. Change the value of a specific cell. It is described by three integers: "t i v", where t = 1 (the type of operation), i — the number of the cell to change and v the value to assign to the cell.
2. Change the value of some subpyramid. The picture shows a highlighted subpyramid with the top in cell 5. It is described by s + 2 numbers: "t i _v_1 _v_2 ... v__s", where t = 2, i — the number of the top cell of the pyramid, s — the size of the subpyramid (the number of cells it has), v__j — the value you should assign to the j-th cell of the subpyramid.

Formally: a subpyramid with top at the i-th cell of the k-th row (the 5-th cell is the second cell of the third row) will contain cells from rows from k to n, the (k + p)-th row contains cells from the i-th to the (i + p)-th (0 ≤ p ≤ n - k).

Vasya and Petya had two identical pyramids. Vasya changed some cells in his pyramid and he now wants to send his changes to Petya. For that, he wants to find a sequence of operations at which Petya can repeat all Vasya's changes. Among all possible sequences, Vasya has to pick the minimum one (the one that contains the fewest numbers).

You have a pyramid of n rows with k changed cells. Find the sequence of operations which result in each of the k changed cells being changed by at least one operation. Among all the possible sequences pick the one that contains the fewest numbers.

瓦西娅和佩佳使用一种有趣的数据存储结构：金字塔。

该金字塔由 $n$ 行组成，第 $i$ 行包含 $i$ 个单元格。每一行相对于上一行向左偏移半个单元格。单元格按整数从 $1$ 到 $\frac{n(n+1)}{2}$ 编号，如下图所示。

当 $n = 5$ 时，一个金字塔示例如下：

该数据结构支持两种类型的操作：

1. 修改某个特定单元格的值。该操作由三个整数描述：“t i v”，其中 $t = 1$（操作类型），$i$ 是待修改单元格的编号，$v$ 是要赋予该单元格的值。
2. 修改某个子金字塔中所有单元格的值。图中高亮显示了一个以第 5 号单元格为顶点的子金字塔。该操作由 $s + 2$ 个整数描述：“t i _v_1 _v_2 ... v__s”，其中 $t = 2$，$i$ 是该子金字塔顶点单元格的编号，$s$ 是该子金字塔的大小（即其所含单元格总数），$v_j$ 是要赋予该子金字塔中第 $j$ 个单元格的值。

形式化定义：设某子金字塔的顶点位于第 $k$ 行的第 $i$ 个单元格（例如第 5 号单元格是第 3 行的第 2 个单元格），则该子金字塔包含从第 $k$ 行到第 $n$ 行的若干单元格；在第 $(k + p)$ 行（其中 $0 \leq p \leq n - k$）中，它包含从第 $i$ 个到第 $(i + p)$ 个单元格。

瓦西娅和佩佳各自拥有一个完全相同的金字塔。瓦西娅修改了他那个金字塔中的若干单元格，现在希望将这些修改同步给佩佳。为此，他需要找出一组操作序列，使得佩佳能通过执行该序列精确复现瓦西娅的所有修改。在所有可行的操作序列中，瓦西娅需选择最短的一个（即所含整数总个数最少的序列）。

现给定一个含 $n$ 行的金字塔，其中有 $k$ 个单元格被修改。请找出一个操作序列，使得这 $k$ 个被修改的单元格中每一个都至少被某次操作修改过。在所有满足条件的序列中，选出所含整数总个数最少的一个。

The first line contains two integers n and k (1 ≤ n, k ≤ 105).

The next k lines contain the coordinates of the modified cells r__i and c__i (1 ≤ c__i ≤ r__i ≤ n) — the row and the cell's number in the row. All cells are distinct.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^5$）。

接下来的 $k$ 行每行包含一个被修改的格子的坐标 $r_i$ 和 $c_i$（$1 \leq c_i \leq r_i \leq n$），分别表示该格子所在的行号及其在该行中的列号。所有格子互不相同。

Print a single number showing how many numbers the final sequence has.

输出一个数字，表示最终序列中包含多少个数。

One of the possible solutions of the first sample consists of two operations:

2 4 _v_4 _v_7 _v_8

2 6 _v_6 _v_9 _v_10

The picture shows the changed cells color-highlighted. The subpyramid used by the first operation is highlighted blue and the subpyramid used by the first operation is highlighted yellow:

第一个样例的一种可能解法包含两次操作：

2 4 _v_4 _v_7 _v_8

2 6 _v_6 _v_9 _v_10

图片中，被修改的单元格以颜色高亮显示。第一次操作所使用的子金字塔以蓝色高亮，第二次操作所使用的子金字塔以黄色高亮：