Задача 4. Супергерой

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

Формат входных данных

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

Формат выходных данных

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

Ограничения

1 ≤ N ≤ 106

1 ≤ fi ≤ M ≤ 109

1 ≤ ti ≤ ti + 1 ≤ 109

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

Стандартный вход Стандартный выход
1
3 3
1 2
2 3
5 1
4
2
100 1
1 100
99
3
1 1
1 1
0

0.102s 0.008s 13