Springboards

Time limit2sMemory limit512 MB

Summary

Given up-and-right springboards that teleport Bessie from (x1,y1) to (x2,y2), find the minimum walking distance from (0,0) to (N,N).

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Binary search, Combinatorics
Solved: No attempts yet

Problem

Bessie is on a 2D grid where she may walk only in directions parallel to one of the coordinate axes. She starts at the point $(0,0)$ and wishes to reach $(N,N)$ ( $1\le N\le 10^9$ ). To help her, there are $P$ springboards on the grid ( $1\le P\le 10^5$ ). Each springboard is at a fixed point $(x_1,y_1)$ , and if Bessie uses it she lands at a point $(x_2,y_2)$ .

Bessie is a progress-oriented cow, so she only permits herself to walk up or right, never left or down. Likewise, each springboard is configured to never go left or down. What is the minimum distance Bessie needs to walk?

Input

The first line 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 \le x_2$ and $y_1 \le y_2$ .

All springboard and target locations are distinct.

Output

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

Hint

Bessie's best path is:

Bessie walks from (0,0) to (0,1) (1 unit).
Bessie springs to (0,2).
Bessie walks from (0,2) to (1,2) (1 unit).
Bessie springs to (2,3).
Bessie walks from (2,3) to (3,3) (1 unit).

The total walking length of Bessie's path is 3 units.

Examples1

Example 1
Input
```
3 2
0 1 0 2
1 2 2 3
```
Expected output
```
3
```