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 ≤ 10^{9}, 1 ≤ K ≤ 18).
The next K lines describe these progressions with two integers b_{i} and d_{i} — the first element and the step of the progression (1 ≤ b_{i}, d_{i} ≤ 10^{9}).
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