스프링보드

Bessie는 2차원 격자 위에 있으며, 이동은 좌표축에 평행한 방향으로만 가능하다. Bessie는 $(0,0)$에서 출발해 $(N,N)$에 도달하려 한다 ($1\le N\le 10^9$). 이를 돕기 위해 격자 위에 $P$개의 스프링보드가 있다 ($1\le P\le 10^5$). 각 스프링보드는 고정된 점 $(x_1,y_1)$에 있고, Bessie가 이를 사용하면 $(x_2,y_2)$에 착지한다.

Bessie는 앞으로 나아가기만 하는 소이므로, 위로 또는 오른쪽으로만 걷고 왼쪽이나 아래로는 걷지 않는다. 마찬가지로 각 스프링보드도 왼쪽이나 아래로 이동하지 않도록 설정되어 있다. Bessie가 걸어야 하는 최소 거리는 얼마인가?

첫째 줄에 두 정수 $N$과 $P$가 공백으로 구분되어 주어진다.

다음 $P$개의 줄 각각에 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. 여기서 $x_1 \le x_2$이고 $y_1 \le y_2$이다.

모든 스프링보드와 목표 지점의 위치는 서로 다르다.

Bessie가 $(N,N)$에 도달하기 위해 걸어야 하는 최소 거리를 정수 하나로 출력한다.

Bessie의 최선 경로는 다음과 같다.

• Bessie가 (0,0)에서 (0,1)까지 걷는다 (1 단위).
• Bessie가 (0,2)로 스프링한다.
• Bessie가 (0,2)에서 (1,2)까지 걷는다 (1 단위).
• Bessie가 (2,3)으로 스프링한다.
• Bessie가 (2,3)에서 (3,3)까지 걷는다 (1 단위).

Bessie 경로의 총 걷기 길이는 3 단위이다.