Раньше Вадиму были интересны только две прогрессии, но теперь у него появились K бесконечных возрастающих арифметических прогрессий. Вадиму стало любопытно, сколько натуральных чисел от 1 до N входят хотя бы в одну из них. Помогите ему посчитать это количество.

Напоминаем, что арифметическая прогрессия — это последовательность чисел вида b, b + d, b + 2d, …, где b — первый элемент прогрессии, d — шаг прогрессии.

В первой строке даны два целых числа N и K — количество рассматриваемых чисел и количество арифметических прогрессий (1 ≤ N ≤ 10⁹, 1 ≤ K ≤ 18).

В следующих K строках описаны эти прогрессии двумя целыми числами b_i и d_i — первый элемент и шаг прогрессии (1 ≤ b_i, d_i ≤ 10⁹).

Выведите одно целое число — количество натуральных чисел от 1 до N, входящих хотя бы в одну арифметическую прогрессию.