Il Gioco del Resto

Facciamo un gioco. Dato un numero iniziale $s_0$ e due sequenze $a_1, a_2, ..., a_n$ e $b_1, b_2, ..., b_n$, l’obiettivo è raggiungere 0 da $s_0$ 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 $s_0$ a 0.

Ingresso

La prima riga dell’ingresso contiene 3 interi n, m e $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000 e 0 < $s_0$ < m).

Le successive n righe contengono una coppia di interi $a_i, b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$).

Uscita

Il programma deve stampare il numero minimo di operazioni per arrivare da $s_0$ a 0. Se non è possibile giungere a 0, il programma deve stampare Impossible.

Esempi