Knapsack in a Globalized World

Time limit2sMemory limit512 MB

Summary

With unlimited copies of n item sizes, decide whether some multiset sums to exactly k, where k can reach 10^18.

Level: Medium7 of 10
Topics: Number theory, Dynamic programming, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
2 10000000000
3 6
```
Expected output
```
impossible
```
Example 2
Input
```
2 10000000000
4 6
```
Expected output
```
possible
```