Minimum Packets Problem

You are given a number of packets, each containing a certain quantity of an ingredient. Your task is to determine the minimum number of packets you need to use in order to accumulate at least a required amount.

For each test case, you will be provided with:

• An integer P representing the number of packets.
• A list of P integers where each integer represents the quantity in a packet.
• An integer R representing the required amount of ingredient.

You are allowed to choose the packets in any order. To solve the problem, the common approach is to sort the list in descending order and then pick the largest quantities until the cumulative sum satisfies the inequality \[ \text{total} \geq R \] . If it is impossible to accumulate at least R even after using all packets, output -1.

inputFormat

The first line contains an integer T, the number of test cases.

Each test case consists of three lines:

• The first line contains an integer P representing the number of packets.
• The second line contains P space-separated integers representing the quantities in each packet.
• The third line contains an integer R denoting the required amount.

outputFormat

For each test case, output a single line containing the minimum number of packets required to reach at least the required amount, or -1 if it is not possible.

1
3
800 400 300
1000

2