1708: [NewOJ Contest 1] 传送阵

内存限制:512 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:14 通过:4

题目描述

玩家小蓝最开始在(0,0),他要去往(n,n),小蓝只能向右走或者向上走。
幸运的是,空间中存在m个传送法阵,可以从(x1,y1)传送到(x2,y2),同时传送阵也不会向左和向下传送。
小蓝每秒钟可以往右走1个单位或者往上走1个单位。
传送阵不耗费任何时间,只要走到传送阵起点,自动穿越到传送阵终点。
求小蓝到达终点的最短时间。

输入格式

输入第一行包含两个正整数n,m(1≤n≤10^9,1≤m≤10^5)。
接下来m行,每行四个整数表示x1,y1,x2,y2,保证x1≤x2,y1≤y2。

输出格式

输出一个数字表示答案。

输入样例 复制

3 2
0 1 0 2
1 2 2 3

输出样例 复制

3