세계화 시대의 배낭

세계화의 물결은 도둑질이라는 유서 깊은 직업에도 밀려왔다. 아무 데나 침입해서 들 수 있는 만큼 챙겨 달아나는 것으로는 이제 부족하다. 경쟁력을 지키려면 이익을 최적화해야 한다.

새로운 규칙은 다음과 같다.

• 아주 큰 상점만 턴다. 어떤 종류의 물건이든 사실상 무한히 쌓여 있다.
• 배낭도 아주 커야 한다.
• 배낭에 빈 공간이 남아서는 안 된다.

규칙을 지키기가 만만치 않아서, 상점을 털 만한지 판단해 주는 프로그램을 짜기로 했다.

상점에는 $n$가지 종류의 물건이 있고, $i$번 종류의 물건 하나는 공간을 정확히 $g_i$만큼 차지한다. 각 종류를 원하는 개수만큼 가져갈 수 있고, 한 개도 가져가지 않아도 된다. 물건을 골라 크기 $k$인 배낭을 빈 공간 없이 정확히 채울 수 있는지 판단하라.

첫째 줄에 물건 종류의 수 $n$과 배낭의 크기 $k$가 주어진다 ($1 \le n \le 20$, $1 \le k \le 10^{18}$).

둘째 줄에 물건 종류별 크기 $g_1, \dots, g_n$이 주어진다 ($1 \le g_i \le 10^3$).

배낭을 빈 공간 없이 채울 수 있으면 possible을, 그렇지 않으면 impossible을 출력한다.