Бессі перебуває в 2D, де дозволено ходити лише у напрямках паралельних одній з координатних вісей. Вона починає з точки ~(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)~.

Бессі - це прогресуюча корова, тому вона дозволяє собі рухатися тільки вгору або вправо, ніколи вліво чи вниз. Так само, кожен трамплін налаштований так, щоб ніколи не йти вліво чи вниз. Яка є мінімальна відстань, яку повинна пройти Бессі?

Input

Перший рядок містить два цілих числа, розділених пробілом, ~N~ та ~P~.

Наступні ~P~ рядків містять чотири цілих числа, ~x_1~, ~y_1~, ~x_2~, ~y_2~, де ~x_1 \le x_2~ та ~y_1 \le y_2.~

Усі місця для трамплінів і кінцеві точки є різними.

Output

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

Оцінювання

Для ~28\%~ балів виконується обмеження ~P \le 1000~.

Sample Input 1

3 2
0 1 0 2
1 2 2 3

Sample Output 1

3

Notes

Найкращий шлях Бессі:

• Бессі йде з (0,0) до (0,1) (1 одиниця).

• Бессі стрибає на (0,2).

• Бессі йде з (0,2) до (1,2) (1 одиниця).

• Бессі стрибає на (2,3).

• Бессі йде з (2,3) до (3,3) (1 одиниця).

Загальна довжина шляху Бессі складає 3 одиниці.