Трамплины
Трамплины
Бесси находится на двумерной решетке, где движение разрешено только параллельно одной из осей координат. Движение она начинает в точке (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.
3 2 0 1 0 2 1 2 2 3
3