Игра с остатком
Давайте поиграем. Пусть у нас есть начальное число и две последовательности , . Вам нужно как можно быстрее преобразовать в 0. На каждом шаге вы можете выбрать индекс
i и применить следующую операцию к текущему числу:Таким образом вы получите новое число. Нужно найти минимальное количество таких операций, чтобы из перейти к 0.
Входные данные
Первая строка содержит три целых числа
n, m и (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000 и 0 < < m).Каждая из следующих
n строк содержит пару целых чисел (0 ≤ , ≤ ).Выходные данные
Программа должна вывести минимальное количество операций, чтобы из получить 0. Если получить 0 невозможно, нужно вывести
Impossible.Примеры
Входные данные | Выходные данные |
2 5 1
3 1
2 1 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB