Minimum Bus Trips

In this problem, you are given several datasets. Each dataset describes the number of students that need to be transported and a set of bus types with different capacities. A bus can be used for multiple trips. Your task is to determine the minimum number of bus trips required to transport all the students. If even using all bus trips the total capacity is insufficient, you should output Impossible.

The problem can be modeled mathematically as follows: Given \(n\) students and bus capacities \(c_1, c_2, \ldots, c_k\), if you choose a bus type with capacity \(c\), the number of trips required is given by \(\lceil \frac{n}{c} \rceil\). The greedy strategy is to use the bus type with the largest capacity first. However, if the sum of all bus capacities (when used in an unbounded number of trips) is less than \(n\), then the answer is Impossible.

inputFormat

The input is read from standard input and begins with an integer \(T\) representing the number of datasets. Each of the following \(T\) lines represents a dataset. Each dataset consists of several space-separated integers. The first integer is \(n\), the number of students. The second integer is \(k\), the number of bus types, followed by \(k\) integers representing the capacities of each bus type.

outputFormat

For each dataset, output the minimum number of bus trips required to transport all students on a separate line. If it is impossible to transport all the students with the given bus capacities, output Impossible.

3
100 3 30 20 50
120 4 10 10 10 10
50 2 40 20

2
Impossible
2