Политическая жизнь одной страны очень оживленная. В стране действует K политических партий, каждая из которых регулярно объявляет национальную забастовку. Дни, когда хотя бы одна из партий объявляет забастовку, при условии, что это не суббота или воскресенье (когда и так никто не работает), наносят большой ущерб экономике страны.
i-я партия объявляет забастовки строго каждые bi дней, начиная с дня с номером ai. То есть i-я партия объявляет забастовки в дни ai, ai+bi, ai+2bi и т.д. Если в какой-то день несколько партий объявляет забастовку, то это считается одной общенациональной забастовкой.
В календаре страны N дней, пронумерованных от 1 до N. Первый день года является понедельником, шестой и седьмой дни года — выходные, неделя состоит из семи дней.
Входные данные
Программа получает на вход число дней в году N (1≤N≤106) и число политических партий K (1≤K≤100). Далее идет K строк, описывающие графики проведения забастовок. i-я строка содержит числа ai и bi (1≤ai,bi≤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
|