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
input | output |
---|
15 2
3 5
6 2
| 7
|
Problem Author: Konstantin Rychkov
Problem Source: Ural School Programming Contest 2022