Задачи
Рюкзак в глобализированном мире
Рюкзак в глобализированном мире
Глобализация не останавливается ни перед чем, даже перед старой доброй честной профессией грабителя. В наше время мало где-то вломиться, взять все, что можно унести, и рвануться прочь. Нет! Вы должны быть конкурентоспособными, оптимизировать прибыль и использовать синергию.
Итак, новые правила игры:
\begin{itemize}
\item взламывать только огромные магазины, где запасы любых предметов практически бесконечны;
\item Ваш рюкзак должен быть огромным;
\item Ваш рюкзак должен быть полным (не должно быть пустого места).
\end{itemize}
Как бы то ни было, но эти правила непросто соблюдать! К счастью, Вы в состоянии написать программу, которая поможет решить, стоит ли грабить магазин или нет.
\InputFile
Первая строка содержт два целых числа $n~(1 \le n \le 20)$ и $k~(1 \le k \le 10^{18})$, где $n$ --- количество различных типов предметов, $k$ --- размер Вашего рюкзака.
Вторая строка содержит $n$ целых чисел $g_1, ..., g_n~(1 \le g_i \le 10^3$ для всех $1 \le i \le n)$, где $g_1, ..., g_n$ --- размеры элементов каждого типа.
\OutputFile
Выведите "\textbf{possible}", если имеется возможность заполнить рюкзак вещами из магазина (считайте что вещей любого типа достаточно много). Иначе выведите "\textbf{impossible}".
Входные данные #1
2 10000000000 3 6
Выходные данные #1
impossible
Входные данные #2
2 10000000000 4 6
Выходные данные #2
possible