페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4146

Springboards 2초 512MB

문제

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?

SCORING:

  • Test cases 2-5 satisfy P \le 1000.

  • Test cases 6-15 satisfy no additional constraints.

Problem credits: Pedro Paredes


입력

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.


출력

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


예제1

입력
3 2
0 1 0 2
1 2 2 3
출력
3

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.


출처

USACO 2020 January Gold

역링크 공식 문제집만