O Jogo do Resto
Vamos jogar um jogo. Dado um número inicial e duas sequências e , o objetivo é chegar de até 0 o mais rápido possível. A cada passo, você pode escolher um índice
i e aplicar a seguinte operação no número atual:Assim, você obtém o próximo número. É preciso determinar o número mínimo de operações necessárias para levar a 0.
Entrada
A primeira linha da entrada contém 3 inteiros
n, m e (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000, e 0 < < m).As próximas
n linhas contêm um par de inteiros (0 ≤ , ≤ ).Saída
O programa deve imprimir o número mínimo de operações necessário para transformar em 0. Se for impossível chegar a 0, deve ser impresso
Impossible.Exemplos
Entrada | Saída |
2 5 1
3 1
2 1 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB