Подорож в місті

У певному місті будинки з одного боку єдиної вулиці мають послідовну нумерацію від $1$ до $N$. Відстань між сусідніми будинками значна, тому жителі зазвичай користуються маршрутними таксі. Є $M$ маршрутних таксі, кожне з яких їздить за власним маршрутом.

Поїздка будь-яким таксі коштує рівно один долар, незалежно від подоланої відстані, але кожне таксі може зупинятися лише біля певних будинків, принаймні двох на маршруті. Зупинки маршруту задаються двома числами: $A$ і $B$. Тут $A$ — найменший номер будинку, біля якого зупиняється це таксі, а $B$ — інтервал між зупинками.

Наприклад, маршрутне таксі з параметрами $2$ та $3$ при N=11 зупиняється біля будинків $2$, $5$, $8$, $11$, $8$, $5$, $2$ і так далі, тож біля деяких будинків таксі може не зупинятися жодного разу.

Враховуючи $N$, $M$ та параметри всіх маршрутів, визначте:

• Скільки будинків залишаються без зупинки жодного таксі.

• Яка мінімальна кількість доларів потрібна, щоб доїхати від першого до $N$-го будинку, або виведіть $0$, якщо це неможливо.

Усі числа $N$, $M$, $A$ і $B$ — натуральні, з обмеженнями 1 \le N \le 200, 1 \le A,B,M \le 20.