eolymp
bolt
Try our new interface for solving problems
Problems

Springboards

Springboards

Time limit 1 second
Memory limit 128 MiB

Bessie is in a 2D grid where walking is permitted only in directions parallel to one of the coordinate axes. She starts at the point (0, 0) and wishes to reach (n, n). To help her out, there are p springboards on the grid. Each springboard is at a fixed point (x[1], y[1]) and if Bessie uses it, she will land 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 nor down. Likewise, each springboard is configured to never go left nor down. What is the minimum distance Bessie needs to walk?

Input data

The fist line contains two integers n (1n10^9) and p (1p10^5). The next p lines each contains four integers x[1], y[1], x[2], y[2], where x[1]x[2] and y[1]y[2].

All springboard and target locations are distinct.

Output data

Print a single integer, the minimum distance Bessie needs to walk to reach (n, n).

Example

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.

Examples

Input example #1
3 2
0 1 0 2
1 2 2 3
Output example #1
3
Source 2020 USACO January, Gold