O Jogo do Resto

Vamos jogar um jogo. Dado um número inicial $s_0$ e duas sequências $a_1, a_2, ..., a_n$ e $b_1, b_2, ..., b_n$, o objetivo é chegar de $s_0$ até 0 o mais rápido possível. A cada passo, você pode escolher um índice i e aplicar a seguinte operação no número atual:

Assim, você obtém o próximo número. É preciso determinar o número mínimo de operações necessárias para levar $s_0$ a 0.

Entrada

A primeira linha da entrada contém 3 inteiros n, m e $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000, e 0 < $s_0$ < m).

As próximas n linhas contêm um par de inteiros $a_i, b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$).

Saída

O programa deve imprimir o número mínimo de operações necessário para transformar $s_0$ em 0. Se for impossível chegar a 0, deve ser impresso Impossible.

Exemplos