The extracurricular life of Masha, Dasha and Misha is very eventful. Together, the children attend
\(K\) circles. The days when a circle is working, parents have to take the children to training after work. If the days of classes are not weekends (Saturday or Sunday), then such days are considered busy.
All circles work through a certain number of days. The i-th circle runs every
\(b_i\) day, starting from the day numbered
\(a_i\). That is, the i-th circle works on the days
\(a_i\),
\(a_i+b_i\) ,
\( a_i+2b_i\) etc.
In the extra class calendar,
\(N\) days are numbered from 1 to
\(N\). The first day is always Monday, the sixth and seventh days are holidays, the week consists of seven days.
Input: The program receives as input the number of days in the calendar
\(N\) (
\(1<=N<=10^6\)) and number of circles
\(K\) (
\(1<=K<=100\)). Next comes
\( K\) lines describing training schedules.
\(i\)th line contains numbers \(a_i\) and \(b_i\) (\(1<=a_i,b_i<=N\)).
Output: print a single number: the number of busy days parents have during the entire class calendar.
Note: The first circle runs on days 2, 5, 8, 11, 14, 17. The second circle runs on days 3, 8, 13, 18. The third circle - on days 9 and 17. Days 6, 7, 13, 14 are days off. So days 2, 3, 5, 8, 9, 11, 17, 18 will be loaded.
Examples
| # |
Input |
Output |
| 1 |
19 3
23
3 5
98 |
8 |