A973.Springboards--Gold

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)$ ($1\le N\le 10^9$). To help her out, there are $P$ ($1\le P\le 10^5$) 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?

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

The fist line contains two space-separated integers $N$ and $P$.
The next $P$ lines each contains 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.

• Test cases 2-5 satisfy $P \le 1000$.
• Test cases 6-15 satisfy no additional constraints.