Knapsack in a Globalized World

Globalization has reached even the old and honest trade of burglary. Breaking in somewhere, grabbing whatever you can carry and running off is no longer enough. To stay competitive you have to optimize your profit.

The new rules are:

• rob only enormous stores, where the supply of every item type is effectively unlimited;
• carry an enormous knapsack;
• leave no empty space in the knapsack.

Those rules are hard to follow, so you write a program that decides whether a store is worth robbing.

The store sells $n$ types of items, and one item of type $i$ takes exactly $g_i$ units of space. You may take any number of items of each type, including none. Decide whether some choice of items fills a knapsack of size $k$ exactly, with no space left over.

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

The second line contains $n$ integers $g_1, \dots, g_n$ ($1 \le g_i \le 10^3$), the sizes of the item types.

Print possible if the items can fill the knapsack exactly, and impossible otherwise.