Внешкольная жизнь Маши, Даши и Миши очень насыщенная. Все вместе дети посещают
\(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 |