3343. [USACO20 Jan Gold] Springboards

【题目描述】

Bessie 在一个仅允许沿平行于坐标轴方向移动的二维方阵中。她从点 $(0,0)$ 出发，想要到达 $(N,N)$（$1\le N\le 10^9$）。为了帮助她达到目的，在方阵中有 $P$（$1\le P\le 10^5$）个跳板。每个跳板都有其固定的位置 $(x_1,y_1)$，如果 Bessie 使用它，会落到点 $(x_2,y_2)$。

Bessie 是一个过程导向的奶牛，所以她仅允许她自己向上或向右行走，从不向左或向下。类似地，每个跳板也设置为不向左或向下。Bessie 需要行走的距离至少是多少？

【输入格式】

输入的第一行包含两个空格分隔的整数 $N$ 和 $P$。

以下 $P$ 行每行包含四个整数 $x_1$、$y_1$、$x_2$、$y_2$，其中 $x_1 \le x_2$ 且 $y_1 \le y_2$。

所有跳板的位置和目标位置均不相同。

【输出格式】

输出一个整数，为 Bessie 到达点 $(N,N)$ 需要行走的最小距离。

【样例1输入】

3 2
0 1 0 2
1 2 2 3

【样例1输出】

3

【样例1解释】

Bessie 的最佳路线为：

• Bessie 从 $(0,0)$ 走到 $(0,1)$（$1$ 单位距离）。
• Bessie 跳到 $(0,2)$。
• Bessie 从 $(0,2)$ 走到 $(1,2)$（$1$ 单位距离）。
• Bessie 跳到 $(2,3)$。
• Bessie 从 $(2,3)$ 走到 $(3,3)$（$1$ 单位距离）。

Bessie 总共走过的路程为 $3$ 单位距离。

【样例2】

点击下载样例2

【数据规模与约定】

对于 $ 33\% $ 的测试数据(测试点$ 1\sim5 $)，满足$ P ≤ 1,000 $。

对于 $ 100\% $ 的测试数据，均满足上文所给出的数据规模。