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.

The first line contains two integers N and K — the number of considered numbers and the number of arithmetic progressions (1 ≤ N ≤ 10⁹, 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⁹).

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