울타리 칠하기

면접 대비

시간 제한2초메모리 제한512 MB

요약

서로 겹치지 않는 구간들을 골라 n개 칸 중 최대한 많이 덮고, 칠해지지 않고 남는 칸 수를 구한다.

난이도: 보통10점 중 6점
유형: 정렬, 동적 계획법, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

널 $n$ 개로 이루어진 울타리를 칠한다. 널에는 1번부터 $n$ 번까지 번호가 붙어 있다. 페인트공 $k$ 명이 각각 정해진 구간 하나를 칠하겠다고 나섰다. 그런데 이들은 서로를 싫어해서, 자기 구간이 다른 페인트공의 구간과 널 한 개라도 겹치면 칠하지 않는다.

구간이 서로 겹치지 않는 페인트공 집합을 골라서 칠하지 못한 널의 개수를 최소로 만들어야 한다. 예를 들어 울타리의 널이 8개이고 페인트공이 3명이며 각각 1번부터 3번, 2번부터 6번, 5번부터 8번을 칠하려 한다고 하자. 첫 번째와 세 번째 페인트공을 고르면 겹치는 구간이 없고, 칠하지 못한 널은 4번 하나뿐이다.

입력

입력은 테스트 케이스 하나로 이루어지며, 같은 프로그램이 서로 다른 입력으로 여러 번 실행될 수 있다. 첫째 줄에 널의 개수 $n$ 과 페인트공의 수 $k$ 가 주어진다 ( $1 \le n \le 10^{18}$ , $1 \le k \le 200000$ ). 다음 $k$ 개 줄에는 각각 정수 $a$ 와 $b$ 가 주어지며 ( $1 \le a \le b \le n$ ), 이 페인트공이 $a$ 번부터 $b$ 번까지의 널을 모두 칠하려 한다는 뜻이다.

출력

페인트공을 겹치지 않게 최적으로 골랐을 때 칠하지 못한 널의 최소 개수를 한 줄에 출력한다.

예제7

예제 1
입력
```
8 3
1 3
2 6
5 8
```
예상 출력
```
1
```
예제 2
입력
```
1 1
1 1
```
예상 출력
```
0
```
예제 3
입력
```
10 1
3 5
```
예상 출력
```
7
```
예제 4
입력
```
10 3
1 10
2 3
4 5
```
예상 출력
```
0
```
예제 5
입력
```
5 3
2 4
2 4
2 4
```
예상 출력
```
2
```
예제 6
입력
```
6 3
1 2
3 4
5 6
```
예상 출력
```
0
```
예제 7
입력
```
10 4
1 4
3 6
5 8
7 10
```
예상 출력
```
2
```