Journey in the City
In a certain city, houses on one side of the only street are numbered consecutively from 1 to N. The distance between neighboring houses is significant, so residents typically use shuttle taxis to get around. There are M shuttle taxis available. Each trip costs just one dollar, regardless of the distance traveled. However, each taxi can only stop at specific houses, with each route having at least two designated stops. The stops for a route are defined by two numbers: A B. Here, A is the smallest house number where the taxi stops, and B is the interval between stops.
For instance, a shuttle taxi with the route 2 3 and N=11 will stop at houses 2, 5, 8, 11, 8, 5, 2, and so on, meaning some houses might not be served by any taxi.
Given the values of N, M, and the details of 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 the journey is impossible.
The values N, M, A, and B are natural numbers, with constraints 1≤N≤200 and 1≤A,B,M≤20.