#C739. Chef's Vegetable Meal Preparation
Chef's Vegetable Meal Preparation
Chef's Vegetable Meal Preparation
You are given T test cases. For each test case, you are provided with two integers N and M. The integer N represents the number of vegetables available, and M represents the minimum total size required to prepare the meal.
The next line contains N integers representing the sizes of the vegetables. The chef can use some or all of them. To determine if the meal is possible, one common strategy is to sort the vegetable sizes in descending order and then select the largest vegetables one by one until the total size is at least M.
Mathematically, let \(a_1, a_2, \ldots, a_N\) be the vegetable sizes sorted in descending order. Find the smallest k such that:
[ \sum_{i=1}^{k} a_i \ge M ]
If such a k exists, output POSSIBLE
; otherwise, output IMPOSSIBLE
.
inputFormat
The input is read from stdin and has the following format:
- The first line contains a single integer
T
, the number of test cases. - For each test case:
- The first line contains two integers
N
andM
whereN
is the number of vegetables andM
is the required meal size. - The second line contains
N
space-separated integers representing the sizes of the vegetables.
outputFormat
For each test case, output one line to stdout containing either POSSIBLE
if the chef can achieve a total vegetable size of at least M, or IMPOSSIBLE
otherwise.
3
5 10
2 3 4 5 1
3 7
2 2 2
4 8
4 3 3 2
POSSIBLE
IMPOSSIBLE
POSSIBLE
</p>