자료 구조

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

요약

행이 10억까지인 삼각뿔에서 M개의 필수 칸이 주어질 때, 채운 모든 칸이 아래 두 지지 칸도 채워지도록 하는 최소 채움 칸 수를 구한다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

컴퓨터 안에서 모든 자료는 자료 블록으로 이루어진 2차원 피라미드에 저장된다.

어떤 피라미드는 행이 $N$ 개이고, 각 행에는 위에서 아래로 $1$ 번부터 $N$ 번까지 번호가 붙는다. $r$ 번 행에는 블록 자리가 $r$ 개 있고, 왼쪽에서 오른쪽으로 $(r, 1)$ 부터 $(r, r)$ 까지 이름이 붙는다. $1$ 번 행부터 $N - 1$ 번 행까지의 블록 자리 $(r, c)$ 는 바로 아래 행의 블록 자리 두 개, 즉 $(r + 1, c)$ 와 $(r + 1, c + 1)$ 위에 놓인다. 아래 그림은 행이 6개인 피라미드이고, 블록 자리 $(3, 1)$ , $(4, 4)$ , $(6, 2)$ 를 빨간색으로 표시했다.

블록 자리는 자료를 담고 있거나 비어 있다. 자료를 담은 블록 자리는 맨 아래 행( $N$ 번 행)에 있거나 자신을 받치는 블록 자리 두 개가 모두 자료를 담고 있을 때만 안정하다. 비어 있지 않은 블록 자리가 모두 안정할 때만 피라미드 전체가 안정하다.

자료를 반드시 담아야 하는 블록 자리가 $M$ 개 있고, 그중 $i$ 번째는 블록 자리 $(r_i, c_i)$ 다. 나머지 블록 자리에는 아무 자료나 담아도 되고 비워 둬도 된다. 자료는 비싸서 되도록 적게 담고 싶다. 필요한 블록 자리 $M$ 개가 모두 자료를 담고 피라미드 전체가 안정할 때, 자료를 담는 블록 자리 개수의 최솟값을 구하라.

입력

첫째 줄에 두 정수 $N$ 과 $M$ 이 주어진다 ( $1 \le N \le 10^9$ , $1 \le M \le 10^5$ ).

다음 $M$ 개 줄에 각각 두 정수 $r_i$ 와 $c_i$ 가 주어진다 ( $1 \le c_i \le r_i \le N$ ). $i$ 번째로 자료를 담아야 하는 블록 자리의 행 번호와 그 행에서의 위치다. 필요한 블록 자리 $M$ 개는 서로 다르다.

출력

피라미드 전체가 안정할 때 자료를 담는 블록 자리 개수의 최솟값을 한 줄에 출력한다. 이 값은 32비트 부호 있는 정수 범위를 넘을 수 있다.

예제5

예제 1
입력
```
6 3
3 1
4 4
6 2
```
예상 출력
```
15
```
예제 2
입력
```
1 1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
2 1
1 1
```
예상 출력
```
3
```
예제 4
입력
```
1000000000 1
1 1
```
예상 출력
```
500000000500000000
```
예제 5
입력
```
1000000000 1
1000000000 1
```
예상 출력
```
1
```