eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рюкзак в глобализированном мире

Рюкзак в глобализированном мире

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Глобализация не останавливается ни перед чем, даже перед старой доброй честной профессией грабителя. В наше время мало где-то вломиться, взять все, что можно унести, и рвануться прочь. Нет! Вы должны быть конкурентоспособными, оптимизировать прибыль и использовать синергию.

Итак, новые правила игры:

  • взламывать только огромные магазины, где запасы любых предметов практически бесконечны;

  • Ваш рюкзак должен быть огромным;

  • Ваш рюкзак должен быть полным (не должно быть пустого места).

Как бы то ни было, но эти правила непросто соблюдать! К счастью, Вы в состоянии написать программу, которая поможет решить, стоит ли грабить магазин или нет.

Вхідні дані

Первая строка содержт два целых числа 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 — размеры элементов каждого типа.

Вихідні дані

Выведите "possible", если имеется возможность заполнить рюкзак вещами из магазина (считайте что вещей любого типа достаточно много). Иначе выведите "impossible".

Приклад

Вхідні дані #1
2 10000000000
3 6
Вихідні дані #1
impossible
Вхідні дані #2
2 10000000000
4 6
Вихідні дані #2
possible
Джерело 2016 German Collegiate Programming Contest (GCPC), Задача C