Беси находится на двумерной решетке, где движение разрешено только параллельно
одной из осей координат. Она начинает в точке \((0,0)\) и хочет достичь точки
\((N,N)\) (\(1\le N\le 10^9\)). Для помощи ей на решетке имеется \(P\) (\(1\le P\le 10^5\))
трамплинов. Каждый трамплин находится в фиксированной точке \((x_1,y_1)\) и
если Беси использует его, она окажется в точке \((x_2,y_2)\).
Беси может двигаться вверх или вправо и никогда влево или вниз. Аналогично
трамплины сконфигурированы так, что никогда не отправляют влево или вниз.
Какое минимальное расстояние Беси должна пройти.
ОЦЕНИВАНИЕ:
- В тестах 2-5 \(P \le 1000\).
- В тестах 6-15 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл boards.in):
Первая строка ввода содержит два разделённых пробелом целых числа
\(N\) и
\(P\).
Каждая из следующих \(P\) строк содержит четыре целых числа \(x_1\), \(y_1\), \(x_2\), \(y_2\),
где \(x_1 \le x_2\) и \(y_1 \le y_2.\)
Все точки начала трамплинов и мест приземления различны.
ФОРМАТ ВЫВОДА (файл boards.out):
Выведите одно целое число, минимальное расстояние, которое Беси должна пройти
чтобы достичь точки \((N,N)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 1 0 2
1 2 2 3
|
3
|