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

Условие

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

Злодей номер 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

Разбор

Идея

Так как злодеи на вход программе передаются последовательно, можно просчитывать только моменты их появления.

Программа просчитывает не каждую секунду, а прыгает от момента появления одного злодея до момента появления следующего.

Для этого нужно лишь знать где находился герой на момент появления предыдущего злодея.

Когда мы побеждаем злодея, то счетчик злодеяний увеличивается на разницу между текущем времени и моментом, когда злодей появился.

Описание алгоритма

Заведем две очереди, в первой будем хранить отсортированных злодеев, которые находятся ниже героя, а во второй тех, что выше.

Когда приходит новый злодей, мы выбираем в какую очередь его добавить и вставляем его туда за O(log N).

Далее моделируем передвижение героя:

t_aim - время, прибытия злодея, t_now - текущее время. Пока текущее меньше, чем время прибытия выбираем куда двигаться, обращаясь к двум очередям и беря из них верхний элемент.

Из очереди достается ближайший враг. Есть 2 варианта: Первый, успеваем добежать, тогда к текущее время увеличивается на разницу между позициями героя и злодея. Второй, не успеваем, тогда время равно времени прибытия злодея. По той же логике - сдвигается текущая позиция героя.

Повторяем, пока не выполнится условие.

Асимптотика алгоритма: O(N log N)