Кружок
(Время: 2 сек. Память: 64 Мб Сложность: 44%)
На занятиях кружка олимпиадного программирования «ШФМ Лаго» доступно n компьютеров, пронумерованных от 1 до n и расположенных по кругу.
Для компьютера с номером i следующим будет являться компьютер с номером i+1, а предыдущим — с номером i−1. При этом, для компьютера n следующим является 1-й, а для компьютера 1 предыдущим является n-й.
В начале учебного года на кружок записалось m учеников. Известно, что i-й ученик в первый день займёт компьютер с номером si, а в каждый последующий день будет пересаживаться. Если di=1, то он будет занимать следующий компьютер, а если di=−1, то предыдущий.
Преподаватель кружка опасается, что если два ученика в один из дней захотят занять один и тот же компьютер, то из-за возможных последствий кружок закроют навсегда. Поэтому, придётся принять в кружок только таких учеников, у которых независимо от количества занятий в кружке не возникнет конфликта ни в какой из дней занятий.
Выясните, какое наибольшее количество учеников смогут заниматься в кружке.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и m – количество компьютеров и количество учеников, соответственно (2 ≤ n ≤ 109; 1 ≤ m ≤ 2×105).
В следующих m строках содержатся числа si и di – номер компьютера в первый день и направление, соответственно (1 ≤ si ≤ n; di=1 или di=−1).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число – наибольшее количество учеников, которых можно принять в кружок.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 6
1 1
2 1
3 1
1 -1
2 -1
3 -1 | 3 |
| 2 | 4 2
1 1
4 -1 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
