Le Jeu du Reste
Jouons à un jeu. Étant donné un nombre initial ainsi que deux séquences et , l’objectif est de transformer en 0 le plus rapidement possible. À chaque étape, vous pouvez choisir un indice
i et appliquer l’opération suivante au nombre courant :De cette manière, vous obtiendrez le nombre suivant. Vous devez déterminer le nombre minimal d’opérations nécessaires pour passer de à 0.
Entrée
La première ligne de l’entrée contient 3 entiers
n, m et (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000, et 0 < < m).Les
n lignes suivantes contiennent chacune une paire d’entiers (0 ≤ , ≤ ).Sortie
Le programme doit afficher le nombre minimal d’opérations pour passer de à 0. S’il est impossible d’atteindre la valeur 0, le programme doit afficher
Impossible.Exemples
Entrée | Sortie |
2 5 1
3 1
2 1 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB