#P6007. [USACO20JAN] Springboards G

[USACO20JAN] Springboards G

题目描述

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

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

输入格式

输入的第一行包含两个空格分隔的整数 NNPP

以下 PP 行每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,其中 x1x2x_1 \leq x_2y1y2y_1 \leq y_2

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

输出格式

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

3 2
0 1 0 2
1 2 2 3
3

提示

样例解释

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 单位距离。

子任务

  • 测试点 252 \sim 5 满足 P1000P \leq 1000
  • 测试点 6156 \sim 15 没有额外限制。