Трампліни#9604

Трампліни

1 секунда

128 мегабайтів

Середня

Бессі знаходиться на двовимірній сітці, де вона може рухатися лише в напрямках, паралельних координатним осям. Вона починає рух з точки $(0, 0)$ і хоче потрапити в точку $(n, n)$ . Щоб допомогти їй, на сітці розташовано $p$ трамплінів. Кожен трамплін починається у фіксованій точці $(x_{1}, y_{1})$ (x_1, y_1) і, якщо Бессі використовує його, переміщує її в точку $(x_{2}, y_{2})$ (x_2, y_2).

Бессі — корова, орієнтована на прогрес, тому вона дозволяє собі рухатися лише вгору або вправо, ніколи не рухаючись вліво або вниз. Аналогічно, кожен трамплін налаштований так, щоб ніколи не переміщувати її вліво або вниз. Іншими словами, для кожного трампліна виконуються умови $x_{1} \leq x_{2}$ x_1 \le x_2 та $y_{1} \leq y_{2}$ y_1 \le y_2.

Яку мінімальну відстань Бессі повинна пройти пішки, щоб досягти точки $(n, n)$ ?

Вхідні дані

У першому рядку містяться два цілих числа $n (1 \leq n \leq 1 0^{9})$ n~(1 \le n \le 10^9) та $p (1 \leq p \leq 1 0^{5})$ p~(1 \le p \le 10^5).

У кожному з наступних $p$ рядків містяться чотири цілих числа $x_{1}, y_{1}, x_{2}, y_{2}$ x_1, y_1, x_2, y_2, що описують трамплін, який переміщує Бессі з точки $(x_{1}, y_{1})$ (x_1, y_1) в точку $(x_{2}, y_{2})$ (x_2, y_2), де виконуються умови $x_{1} \leq x_{2}$ x_1 \le x_2 та $y_{1} \leq y_{2}$ y_1 \le y_2.

Усі початкові та кінцеві точки трамплінів, а також цільова точка різні.

Вихідні дані

Виведіть одне ціле число — мінімальну відстань, яку Бессі повинна пройти пішки, щоб досягти точки $(n, n)$ .

Приклади

Оптимальний маршрут Бессі виглядає так:

Бессі йде з точки $(0, 0)$ в точку $(0, 1)$ , проходячи відстань $1$ .
Бессі використовує трамплін, щоб переміститися з точки $(0, 1)$ в точку $(0, 2)$ .
Бессі йде з точки $(0, 2)$ в точку $(1, 2)$ , проходячи відстань $1$ .
Бессі використовує трамплін, щоб переміститися з точки $(1, 2)$ в точку $(2, 3)$ .
Бессі йде з точки $(2, 3)$ в точку $(3, 3)$ , проходячи відстань $1$ .

Загальна довжина шляху, пройденого пішки, становить $3$ одиниці.

Приклад 1