Задача A. Tower Defence ≡

Условие

Юный супергерой Вася однажды выяснил, что на один из небоскрёбов его города (состоящий из M этажей, пронумерованных от 1 до M) планирует напасть группа из N злодеев. Вася прибыл на первый этаж непосредственно перед началом нападения злодеев и приготовился его отражать.

Злодей номер i появляется на этаже f_i через t_i секунд после начала нападения, и начинает творить зло со скоростью одно злое дело в секунду.

Каждую секунду Вася проделывает следующие действия:

1. Если на текущем этаже находятся злодеи, обезвреживает их.
2. Сдвигается вниз или вверх на один этаж по направлению к ближайшему злодею.
3. Если расстояния равны, Вася предпочитает подниматься вверх.
4. Если в текущий момент ни одного активного злодея в небоскрёбе нет, Вася остаётся на текущем этаже.

Требуется определить, сколько злых дел успеют совершить все злодеи в сумме.

Формат входного файла

Входной файл содержит целые числа M N, за которыми следует N пар целых чисел t_i f_i.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество злых дел.

Ограничения

1 ≤ N ≤ 10⁶;

1 ≤ f_i ≤ M ≤ 10⁹;

1 ≤ t_i ≤ t_i + 1 ≤ 10⁹;

Примеры тестов

3 3
1 2
2 3
5 1

4

100 1
1 100

99

1 1
1 1

0