시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB71564679.310%

문제

When creating a gift bag, you are trying to create a bag that weighs as much as possible with as few items as possible. This is to make it feel like the guests are receiving a lot without having to use as many items in each gift bag. Instead of finding how much to put in each gift bag, write a program that finds the fewest number of items you can put into a gift bag to reach the recommended value.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will be three lines, and will start with a single integer x denoting the number of items. The next line will contain x integers, indicating the weight of each item. The next line will be a single integer indicating the total weight you are trying to reach.

출력

Output the smallest number of items that will add up to the weight to be returned. If it is not possible to add up exactly to the weight to be returned, print Not possible.

예제 입력 1

3
10
1 3 3 3 5 7 7 5 5 10
39
10
1 2 3 4 5 6 7 8 9 10
27
1
100
50

예제 출력 1

6
3
Not possible