Das Rest-Spiel

Lass uns ein Spiel spielen. Gegeben ist eine Anfangszahl $s_0$ sowie zwei Sequenzen $a_1, a_2, ..., a_n$ und $b_1, b_2, ..., b_n$. Das Ziel ist, so schnell wie möglich von $s_0$ auf 0 zu gelangen. In jedem Schritt darfst du einen Index i wählen und die folgende Operation auf die aktuelle Zahl anwenden:

Auf diese Weise erhältst du die nächste Zahl. Du sollst die minimale Anzahl von Operationen bestimmen, um von $s_0$ auf 0 zu kommen.

Eingabe

Die erste Zeile der Eingabe enthält 3 ganze Zahlen n, m und $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000 und 0 < $s_0$ < m).

Die nächsten n Zeilen enthalten jeweils ein Paar von ganzen Zahlen $a_i$ und $b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$).

Ausgabe

Das Programm soll die minimale Anzahl an Operationen ausgeben, um von $s_0$ auf 0 zu gelangen. Ist es unmöglich, 0 zu erreichen, soll das Programm Impossible ausgeben.

Beispiele