Bessie’s Minimum Walking Distance

Bessie is trapped in a 2D grid, where she may only move upward or to the right. She starts at \( (0,0) \) and wants to reach \( (N,N) \) (with \( 1 \le N \le 10^9 \)). Scattered around the grid are \( P \) jump pads (\( 1 \le P \le 10^5 \)). Each jump pad is located at \( (x_1, y_1) \) and if used, immediately transports Bessie to \( (x_2, y_2) \). Both Bessie's moves and the jump pads move in non‐decreasing directions (i.e. neither left nor downward).

When Bessie walks, she covers Manhattan distance. That is, walking from \( (a,b) \) to \( (c,d) \) costs \( (c-a) + (d-b) \). However, when using a jump pad, she instantly moves from \( (x_1, y_1) \) to \( (x_2, y_2) \) at no walking cost. Note that each jump pad itself is configured such that \( x_2 \ge x_1 \) and \( y_2 \ge y_1 \).

Your task is to help Bessie choose an optimal plan so that the total distance she has to walk is minimized. Formally, let the total walking distance (if no jump pads are used) be \( 2N \). Each jump pad from \( (x_1,y_1) \) to \( (x_2,y_2) \) gives a potential saving of \( (x_2 - x_1) + (y_2 - y_1) \) units. However, Bessie can only chain jump pads if the destination of the previous jump is not later than the start of the next jump (in both coordinates). Determine the minimum distance Bessie must walk if she uses the jump pads optimally.

Input constraints:

• \( 1 \le N \le 10^9 \)
• \( 1 \le P \le 10^5 \)
• All coordinates satisfy \( 0 \le x_1, y_1, x_2, y_2 \le N \) and the jump move is non-decreasing.

inputFormat

The first line contains two integers \( N \) and \( P \): the grid size and the number of jump pads.

Then \( P \) lines follow, each containing four integers: \( x_1\, y_1\, x_2\, y_2 \) representing a jump pad that transports from \( (x_1,y_1) \) to \( (x_2,y_2) \).

You can assume that all jump pads satisfy \( x_1 \le x_2 \) and \( y_1 \le y_2 \), and all coordinates are within \( [0, N] \).

outputFormat

Output a single integer: the minimum walking distance Bessie must cover to reach \( (N,N) \) when using the jump pads optimally.

sample

5 2
1 1 3 3
3 3 4 4

4