Бесси находится на двумерной решетке, где движение разрешено только параллельно одной из осей координат. Движение она начинает в точке (0, 0) и хочет достичь точки (n, n). На решетке имеется p трамплинов. Каждый трамплин находится в фиксированной точке (x1, y1) и если Бесси использует его, то она окажется в точке (x2, y2).

Бесси может передвигаться вверх или вправо и никогда влево или вниз. Аналогично трамплины сконфигурированы так, что никогда не отправляют влево или вниз. Вычислите минимальное расстояние, которое Бесси должна пройти.

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 109) и p (1 ≤ p ≤ 105). Каждая из следующих p строк содержит четыре целых числа x1, y1, x2, y2, где x1 ≤ x2 и y1 ≤ y2.

Все точки начала трамплинов и мест приземления различны.

Выходные данные

Выведите одно целое число - минимальное расстояние, которое Бесси должна пройти чтобы достичь точки (n, n).

Пример

Оптимальный маршрут таков:

• Пешком из (0, 0) в (0, 1) (1).
• Прыжком в (0, 2).
• Пешком из (0, 2) в (1, 2) (1).
• Прыжком в (2, 3).
• Пешком из (2, 3) в (3, 3) (1).

Суммарная длина пути пройденного пешком = 3.