Data Structure

Inside a computer, every piece of data is stored in a two-dimensional pyramid of data blocks.

One such pyramid has $N$ rows, numbered $1$ through $N$ from top to bottom. Row $r$ has $r$ block spaces, labelled $(r, 1)$ through $(r, r)$ from left to right. Every block space $(r, c)$ in rows $1$ through $N - 1$ rests on two supporting block spaces in the row below it, namely $(r + 1, c)$ and $(r + 1, c + 1)$. The picture below shows a pyramid with 6 rows, with the block spaces $(3, 1)$, $(4, 4)$ and $(6, 2)$ marked in red.

Each block space either contains data or is empty. A block space that contains data is stable only if it is in the bottom row (row $N$), or if both of its two supporting block spaces also contain data. The whole pyramid is stable only if all of its non-empty block spaces are stable.

There are $M$ block spaces that must contain data, and the $i$-th of them is block space $(r_i, c_i)$. Every other block space of the pyramid may be filled with arbitrary data or be left empty. Data is expensive, so you want the smallest possible amount of it. Find the smallest number of block spaces that can contain data while all $M$ required block spaces contain data and the entire pyramid is stable.

The first line contains two integers $N$ and $M$ ($1 \le N \le 10^9$, $1 \le M \le 10^5$).

Each of the next $M$ lines contains two integers $r_i$ and $c_i$ ($1 \le c_i \le r_i \le N$), the row and the position within that row of the $i$-th required block space. The $M$ required block spaces are distinct.

Print one integer, the smallest number of block spaces that can contain data such that the entire pyramid is stable. This value may not fit in a 32-bit signed integer.