eolymp
bolt
Try our new interface for solving problems
Problems

Knapsack in a Globalized World

Knapsack in a Globalized World

Time limit 1 second
Memory limit 128 MiB

Globalization stops at nothing, not even at the good old honest profession of a burglar. Nowadays it is not enough to break in somewhere, take everything you can carry and dart off. No! You have to be competitive, optimise your profit and utilise synergies.

So, the new game rules are:

  • break only into huge stores, so there is practically endless supply of any kind of items;

  • your knapsack should be huge;

  • your knapsack should be full (there should be no empty space left).

Damn you, globalisation, these rules are not easy to follow! Luckily, you can write a program, which will help you decide whether you should loot a store or not.

Input data

The first line contains two integers n~(1 \le n \le 20) and k~(1 \le k \le 10^{18}), where n is the number of different item types and k is the size of your knapsack.

The second line contains n integers g_1, ..., g_n~(1 \le g_i \le 10^3 for all 1 \le i \le n)), where g_1, ..., g_n are the sizes of the n item types.

Output data

Output "possible" if it is possible to fill your knapsack with items from the store (you may assume that there are enough items of any type), otherwise output "impossible".

Examples

Input example #1
2 10000000000
3 6
Output example #1
impossible
Input example #2
2 10000000000
4 6
Output example #2
possible
Source 2016 German Collegiate Programming Contest (GCPC), Problem C