El Juego del Resto

Vamos a jugar un juego. Dado un número inicial $s_0$ y dos secuencias $a_1, a_2, ..., a_n$ y $b_1, b_2, ..., b_n$, tu objetivo es llegar desde $s_0$ hasta 0 lo más rápido posible. En cada paso, puedes elegir un índice i y aplicar la siguiente operación al número actual:

Así obtendrás el siguiente número. Debes encontrar el número mínimo de operaciones necesarias para pasar de $s_0$ a 0.

Entrada

La primera línea de la entrada contiene 3 enteros n, m y $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000, y 0 < $s_0$ < m).

Las siguientes n líneas contienen un par de enteros $a_i, b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$).

Salida

El programa debe imprimir el número mínimo de operaciones para llegar desde $s_0$ a 0. Si resulta imposible llegar a 0, el programa debe mostrar Impossible.

Ejemplos