Le Jeu du Reste

Jouons à un jeu. Étant donné un nombre initial $s_0$ ainsi que deux séquences $a_1, a_2, ..., a_n$ et $b_1, b_2, ..., b_n$, l’objectif est de transformer $s_0$ 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 $s_0$ à 0.

Entrée

La première ligne de l’entrée contient 3 entiers n, m et $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000, et 0 < $s_0$ < m).

Les n lignes suivantes contiennent chacune une paire d’entiers $a_i, b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$).

Sortie

Le programme doit afficher le nombre minimal d’opérations pour passer de $s_0$ à 0. S’il est impossible d’atteindre la valeur 0, le programme doit afficher Impossible.

Exemples