Springboards#9604
Bessie is in a 2D grid where she can walk only in directions parallel to the coordinate axes. She starts at the point and wants to reach . To help her, there are springboards placed on the grid. Each springboard starts at a fixed point (x_1, y_1) and, when Bessie uses it, transports her to the point (x_2, y_2).
Bessie is a progress-oriented cow, so she only allows herself to walk up or right, never left or down. Similarly, each springboard is configured to never move her left or down. In other words, for every springboard, x_1 \le x_2 and y_1 \le y_2.
What is the minimum distance Bessie needs to walk to reach ?
The first line contains two integers n~(1 \le n \le 10^9) and p~(1 \le p \le 10^5).
Each of the next lines contains four integers x_1, y_1, x_2, y_2, describing a springboard that transports Bessie from (x_1, y_1) to (x_2, y_2), where x_1 \le x_2 and y_1 \le y_2.
All springboard endpoints and the target point are distinct.
Print one integer — the minimum distance Bessie needs to walk to reach .
Bessie's best path is as follows:
Bessie walks from to , a distance of unit.
Bessie uses a springboard to travel from to .
Bessie walks from to , a distance of unit.
Bessie uses a springboard to travel from to .
Bessie walks from to , a distance of unit.
The total walking distance is units.
Example 1