Il Gioco del Resto
Facciamo un gioco. Dato un numero iniziale e due sequenze e , l’obiettivo è raggiungere 0 da nel minor numero di mosse possibile. A ogni passo, si può scegliere un indice
i ed eseguire la seguente operazione sul numero corrente:In questo modo si ottiene il numero successivo. Bisogna trovare il numero minimo di operazioni richieste per portare a 0.
Ingresso
La prima riga dell’ingresso contiene 3 interi
n, m e (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000 e 0 < < m).Le successive
n righe contengono una coppia di interi (0 ≤ , ≤ ).Uscita
Il programma deve stampare il numero minimo di operazioni per arrivare da a 0. Se non è possibile giungere a 0, il programma deve stampare
Impossible.Esempi
Ingresso | Uscita |
2 5 1
3 1
2 1 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB