움직이는 칸

어린 앨리스가 생일 선물로 현대적인 픽셀 그림을 받았다.

그림은 크기가 $n\times m$인 직사각형 격자이다. 격자의 각 열에는 연속된 칸 하나 이상이 검은색으로 칠해져 있고, 나머지 칸은 모두 흰색이다.

앨리스는 임의의 두 검은색 칸 $u$와 $v$ 사이에 검은색 칸만 지나며 변을 공유하는 칸으로 이동하는 경로가 있으면 그림이 아름답다고 본다. 경로는 $u$에서 시작해 $u$와 변으로 인접한 검은색 칸 $w$로 가고, 다시 $w$와 인접한 검은색 칸으로 이동하기를 반복해 $v$에 도달한다.

한 번의 행동에서 임의의 열을 하나 골라 그 열의 검은색 칸을 모두 위 또는 아래 방향으로 한 칸 옮길 수 있다. 칸이 그림 밖으로 나가지 않는 경우에만 옮길 수 있다.

그림을 아름답게 만드는 데 필요한 행동 횟수의 최솟값을 구하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다. 각각 그림의 행 수와 열 수이다 ($1 \le n, m \le 100\,000$). 그림의 전체 칸 수는 $10^{6}$을 넘지 않는다 ($1 \le n \cdot m \le 1\,000\,000$).

다음 $m$개의 줄에는 각각 두 정수 $s_i$와 $t_i$가 주어진다. 이는 $i$번째 열에서 검은색 칸의 시작 행과 끝 행이다 ($1 \le s_i \le t_i \le n$).

그림을 아름답게 만드는 데 필요한 행동 횟수의 최솟값을 한 줄에 출력한다.