Олимпиадный тренинг

Задача . Тренировки


Задача

Темы: Множества
Внешкольная жизнь Маши, Даши и Миши очень насыщенная. Все вместе дети посещают \(K\) кружков. Дни, когда работает какой-либо кружок, родителям после работы приходится отвозить ребят на тренировки. Если дни занятий не выходные (суббота или воскресенье), то такие дни считаются загруженными.
Все кружки работают через определенное число дней. i-й кружок работает каждый \(b_i\) день, начиная с дня c номером \(a_i\). То есть i-й кружок работает в дни \(a_i\), \(a_i+b_i\)\( a_i+2b_i\) и т.д. 
В календаре дополнительных занятий \(N\) дней, пронумерованных от 1 до \(N\). Первый день всегда понедельник, шестой и седьмой дни - выходные, неделя состоит из семи дней.

Входные данные: программа получает на вход число дней в календаре \(N\) (\(1<=N<=10^6\)) и число кружков \(K\) (\(1<=K<=100\)). Далее идет \( K\) строк, описывающие графики проведения тренировок. \(i\)-я строка содержит числа \(a_i\) и \(b_i\) (\(1<=a_i,b_i<=N\)).

Выходные данные: выведите единственное число: количество загруженных дней у родителей в течение всего календаря занятий.

Примечание: первый кружок работает в дни 2, 5, 8, 11, 14, 17. Второй кружок работает в дни 3, 8, 13, 18. Третий кружок - в дни 9 и 17. Дни номер 6, 7, 13, 14 являются выходными. Таким образом, загруженными будут дни 2, 3, 5, 8, 9, 11, 17, 18. 

 

Примеры
Входные данные Выходные данные
1 19 3
2 3
3 5
9 8
8

 


time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6413
Python25
Комментарий учителя