Problem Description

Bessie is in a two-dimensional grid where she is only allowed to move in directions parallel to the coordinate axes. She starts at point $(0,0)$ and wants to reach $(N,N)$ ($1 \leq N \leq 10^9$). To help her, there are $P$ ($1 \leq P \leq 10^5$) springboards in the grid. Each springboard has a fixed position $(x_1,y_1)$, and if Bessie uses it, she will land at point $(x_2,y_2)$.

Bessie is a process-oriented cow, so she is only allowed to walk up or right, never left or down. Similarly, each springboard is also set up so that it does not go left or down. What is the minimum distance Bessie needs to walk?

Input Format

The first line of input contains two space-separated integers $N$ and $P$.

The next $P$ lines each contain four integers $x_1,y_1,x_2,y_2$, where $x_1 \leq x_2$ and $y_1 \leq y_2$.

All springboard positions and landing positions are distinct.

Output Format

Output one integer, the minimum distance Bessie needs to walk to reach point $(N,N)$.

3 2
0 1 0 2
1 2 2 3

3

Hint

Sample Explanation

Bessie's best route is:

• Bessie walks from (0,0) to (0,1) (distance 1).
• Bessie jumps to (0,2).
• Bessie walks from (0,2) to (1,2) (distance 1).
• Bessie jumps to (2,3).
• Bessie walks from (2,3) to (3,3) (distance 1).

In total, Bessie walks a distance of 3.

Subtasks

• Test cases $2 \sim 5$ satisfy $P \leq 1000$.
• Test cases $6 \sim 15$ have no additional constraints.

Translated by ChatGPT 5