eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В деякому місті будинки, що знаходяться по одну сторону єдиної вулиці пронумеровані послідовними числами від 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 - натуральні, 1N200, 1A,B,M20.

Пример

Входные данные #1
11 2
2 3
1 4
Выходные данные #1
5 2
Автор Матвійчук С.В.
Источник III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2015-2016 р