Painting the fence

Interview

Time limit2sMemory limit512 MB

Summary

Pick a pairwise non-overlapping set of intervals to cover as many of the n slats as possible, then report the number left unpainted.

Level: Medium6 of 10
Topics: Sorting, Dynamic programming, Binary search, Prefix sum
Solved: No attempts yet

Problem

You are painting a picket fence made of $n$ slats, numbered 1 to $n$ . Each of $k$ painters has offered to paint one fixed range of slats. They dislike each other, so a painter refuses the job if another painter's range overlaps their own range by even one slat.

Choose a set of painters whose ranges do not overlap, so that the number of unpainted slats is as small as possible. Suppose the fence has 8 slats and there are 3 painters, who want to paint slats 1 to 3, 2 to 6, and 5 to 8. Picking the first painter and the third painter creates no overlap and leaves only slat 4 unpainted.

Input

Each input consists of a single test case, and the same program may be run several times on different inputs. The first line contains two integers $n$ and $k$ ( $1 \le n \le 10^{18}$ , $1 \le k \le 200000$ ), 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$ ), meaning that this painter wants to paint every slat from $a$ to $b$ , inclusive.

Output

Print one integer, the smallest number of slats that stay unpainted when the painters are chosen optimally without overlap.

Examples7

Example 1
Input
```
8 3
1 3
2 6
5 8
```
Expected output
```
1
```
Example 2
Input
```
1 1
1 1
```
Expected output
```
0
```
Example 3
Input
```
10 1
3 5
```
Expected output
```
7
```
Example 4
Input
```
10 3
1 10
2 3
4 5
```
Expected output
```
0
```
Example 5
Input
```
5 3
2 4
2 4
2 4
```
Expected output
```
2
```
Example 6
Input
```
6 3
1 2
3 4
5 6
```
Expected output
```
0
```
Example 7
Input
```
10 4
1 4
3 6
5 8
7 10
```
Expected output
```
2
```