Paint

You are painting a picket fence with $n$ slats, numbered from $1$ to $n$. There are $k$ painters willing to paint a specific portion of the fence. However, they donâ€™t like each other, and each painter will only paint their given portion of the fence if no other painter overlaps their portion.

You want to select a subset of painters that do not conflict with each other, in order to minimize the number of unpainted slats. For example, suppose there are $8$ slats, and $3$ painters. One painter wants to paint slats $1 \rightarrow 3$, one wants to paint $2 \rightarrow 6$, and one wants to paint $5 \rightarrow 8$. By choosing the first and last painters, you can paint most of the slats, leaving only a single slat (slat $4$) unpainted, with no overlap between painters.

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two integers $n$ ($1 \le n \le 10^{18}$) and $k$ ($1 \le k \le 200\, 000$), where $n$ is the number of slats and $k$ is the number of painters. Each of the next $k$ lines contains two integers $a$ and $b$ ($1 \le a \le b \le n$), indicating that this painter wants to paint all of the slats between $a$ and $b$, inclusive.

Output a single integer, which is the smallest number of slats that go unpainted with an optimal selection of painters.

Sample Input 1 | Sample Output 1 |
---|---|

8 3 1 3 2 6 5 8 |
1 |