Рюкзак в глобализированном мире
Рюкзак в глобализированном мире
Глобализация не останавливается ни перед чем, даже перед старой доброй честной профессией грабителя. В наше время мало где-то вломиться, взять все, что можно унести, и рвануться прочь. Нет! Вы должны быть конкурентоспособными, оптимизировать прибыль и использовать синергию.
Итак, новые правила игры:
взламывать только огромные магазины, где запасы любых предметов практически бесконечны;
Ваш рюкзак должен быть огромным;
Ваш рюкзак должен быть полным (не должно быть пустого места).
Как бы то ни было, но эти правила непросто соблюдать! К счастью, Вы в состоянии написать программу, которая поможет решить, стоит ли грабить магазин или нет.
Вхідні дані
Первая строка содержт два целых числа 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".
Приклад
2 10000000000 3 6
impossible
2 10000000000 4 6
possible