410774: GYM104101 G Red Black Tree

给一个拥有 $$$n$$$ 层的红黑树，第一层有一片叶子，第二层有两片叶子....第 $$$n$$$ 层有 $$$n$$$ 片叶子。第 $$$i$$$ 行第 $$$j$$$ 片叶子表示为 $$$(i, j)$$$ ， 如下图1.1，所以除了第 $$$n$$$ 层的叶子之外，每一片叶子下面都拥有两片叶子，即叶子 $$$(i, j)$$$ 下面的叶子是 $$$(i+1,j)$$$ 和 $$$(i+1,j+1)$$$ 。

图1.1

之后给定 $$$k$$$ 片叶子的位置 $$$(x, y)$$$，表示该叶子为黑色，其他叶子为红色。

现给定两条规则

• 若叶子为黑色，则它下面两片叶子也要为黑色。
• 若它下面两片叶子都是黑色，则它也要为黑色。

现在可以将部分红色叶子染黑，使得每一个黑色叶子都满足上面的规则，同时让染黑的叶子数量最少。

问最终树上黑色叶子数量是多少?

第一行包含两个整数 $$$n, k\ (1 \le n \le 10^6;1 \le k \le min(10^6, \frac{n \times (n + 1)}{2}))$$$ — 表示层数和初始黑色叶子的数量。

接下来 $$$k$$$ 行，每行包含两个整数 $$$x, y\ (1\le y \le x \le n)$$$ — 表示黑色叶子的位置在 $$$(x, y)$$$，数据保证不重复。

输出最终树上黑色叶子的数量。

5 3
2 1
3 1
4 1

10

3 1
1 1

6