Путешествие в городе
В некотором городе дома, расположенные на одной стороне единственной улицы, пронумерованы последовательными числами от 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≤N≤200, 1≤A,B,M≤20.