Игра с остатком

Давайте поиграем. Пусть у нас есть начальное число $s_0$ и две последовательности $a_1, a_2, ..., a_n$, $b_1, b_2, ..., b_n$. Вам нужно как можно быстрее преобразовать $s_0$ в 0. На каждом шаге вы можете выбрать индекс i и применить следующую операцию к текущему числу:

Таким образом вы получите новое число. Нужно найти минимальное количество таких операций, чтобы из $s_0$ перейти к 0.

Входные данные

Первая строка содержит три целых числа n, m и $s_0$ (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000 и 0 < $s_0$ < m).

Каждая из следующих n строк содержит пару целых чисел $a_i, b_i$ (0 ≤ $a_i$, $b_i$ ≤ $10^9$).

Выходные данные

Программа должна вывести минимальное количество операций, чтобы из $s_0$ получить 0. Если получить 0 невозможно, нужно вывести Impossible.

Примеры