Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Кружок

(Время: 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.TXTOUTPUT.TXT
13 6
1 1
2 1
3 1
1 -1
2 -1
3 -1
3
24 2
1 1
4 -1
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Вы все уже победители
 B. Заработай себе металлолома
 C. Обледенение
 D. Дата сайнс
 E. Вирусные воспоминания
 F. Докраска забора
 G. Скатерть
 H. История одного анекдота
 I. Кружок
 J. JuryGPT

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ICQ: 151483, E-mail: admin@acmp.ru



Домен losix.ru: купить в магазине доменных имен Рег.ру