자료 구조

컴퓨터 안에서 모든 자료는 자료 블록으로 이루어진 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비트 부호 있는 정수 범위를 넘을 수 있다.