ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2171. Two Progressions 2

Time limit: 2.0 second
Memory limit: 256 MB
Previously, Vadim was only interested in two progressions, but now he has K infinite increasing arithmetic progressions. Vadim is curious to know how many natural numbers from 1 to N are included in at least one of these progressions. Help him count this number.
Note that an arithmetic progression is a sequence of numbers of the form b, b + d, b + 2d, …, where b is the first element of the progression and d is the progression step.

Input

The first line contains two integers N and K — the number of considered numbers and the number of arithmetic progressions (1 ≤ N ≤ 109, 1 ≤ K ≤ 18).
The next K lines describe these progressions with two integers bi and di — the first element and the step of the progression (1 ≤ bi, di ≤ 109).

Output

Output a single integer — the number of natural numbers from 1 to N that are included in at least one arithmetic progression.

Sample

inputoutput
15 2
3 5
6 2
7
Problem Author: Konstantin Rychkov
Problem Source: Ural School Programming Contest 2022