Journey in the City

In a certain city, the houses on one side of the only street are numbered consecutively from $1$ to $N$. The distance between neighboring houses is significant, so residents usually travel by shuttle taxis. There are $M$ shuttle taxis, each operating on its own route.

A trip by any taxi costs exactly one dollar, regardless of the distance traveled, but each taxi can stop only at specific houses, at least two per route. The stops for a route are specified by two numbers: $A$ and $B$. Here, $A$ is the smallest house number where the taxi stops, and $B$ is the period between stops.

For example, a shuttle taxi with parameters $2$ and $3$ for N=11 will stop at houses $2$, $5$, $8$, $11$, $8$, $5$, $2$, and so on, so some houses may have no taxi stopping at them.

Given $N$, $M$, and the parameters for all routes, determine:

• The number of houses where no taxi stops.

• The minimum number of dollars required to travel from the first house to the $N$-th house, or output $0$ if it is impossible.

All numbers $N$, $M$, $A$, and $B$ are natural numbers, with constraints 1 \le N \le 200, 1 \le A,B,M \le 20.