Трамплины
Бесси находится на двумерной решетке, где движение разрешено только параллельно одной из осей координат. Движение она начинает в точке (0, 0) и хочет достичь точки (n, n). На решетке имеется p трамплинов. Каждый трамплин находится в фиксированной точке (x[1], y[1]) и если Бесси использует его, то она окажется в точке (x[2], y[2]).
Бесси может передвигаться вверх или вправо и никогда влево или вниз. Аналогично трамплины сконфигурированы так, что никогда не отправляют влево или вниз. Вычислите минимальное расстояние, которое Бесси должна пройти.
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 10^9) и p (1 ≤ p ≤ 10^5). Каждая из следующих p строк содержит четыре целых числа x[1], y[1], x[2], y[2], где x[1] ≤ x[2] и y[1] ≤ y[2].
Все точки начала трамплинов и мест приземления различны.
Выходные данные
Выведите одно целое число - минимальное расстояние, которое Бесси должна пройти чтобы достичь точки (n, n).
Пример
Оптимальный маршрут таков:
Пешком из (0, 0) в (0, 1) (1).
Прыжком в (0, 2).
Пешком из (0, 2) в (1, 2) (1).
Прыжком в (2, 3).
Пешком из (2, 3) в (3, 3) (1).
Суммарная длина пути пройденного пешком = 3.