Задача A. Tower Defence

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106;

1 ≤ fi ≤ M ≤ 109;

1 ≤ ti ≤ ti + 1 ≤ 109;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 2
2 3
5 1
4
2
100 1
1 100
99
3
1 1
1 1
0

0.088s 0.017s 13