Minimum Trucks Deployment Problem

You are given N outposts, each requiring a certain amount of supplies, and M trucks, each with a maximum carrying capacity. Your goal is to determine the minimum number of trucks needed to deliver all the supplies. A truck can deliver supplies to one or more outposts until its capacity is exhausted. If the total available truck capacity is insufficient to cover the total supplies required, the answer should be -1.

The delivery process is modeled as follows. First, the supply requirements and truck capacities are sorted (supplies in ascending order and trucks in descending order). Then, each truck is used sequentially: while a truck has remaining capacity and there are still supply requirements to fulfill, the truck will either completely satisfy an outpost's requirement if possible or partially deliver supplies, reducing the pending amount. Formally, let \(S = [s_1, s_2, \dots, s_N]\) be the sorted supply requirements and \(T = [t_1, t_2, \dots, t_M]\) be the truck capacities sorted in descending order. The process continues until all supplies are delivered or no further deliveries can be made. The answer is the number of trucks used if delivery is possible, otherwise \(-1\).

Input Format: The input is read from stdin and consists of multiple test cases. The first line contains a single integer T, the number of test cases. For each test case, the first line contains two integers N and M. The second line contains N integers indicating the supplies required at each outpost. The third line contains M integers representing the capacities of the trucks.

Output Format: For each test case, output a single integer on a new line — the minimum number of trucks required to deliver all supplies, or -1 if it is impossible.

inputFormat

The input is provided via standard input (stdin) with the following format:

T
N M
s1 s2 ... sN
t1 t2 ... tM
... (repeated for T test cases)

Where:

• T is the number of test cases.
• For each test case, N is the number of outposts and M is the number of trucks.
• si represents the supply requirement at the i-th outpost.
• tj represents the capacity of the j-th truck.

outputFormat

Output to standard output (stdout) the minimum number of trucks required for each test case on separate lines. If it is impossible to deliver all supplies, output -1.

## sample

3
3 4
10 10 10
5 5 5 5
2 2
20 10
30 20
5 5
5 10 15 20 25
30 30 30 30 30

-1
1
3

</p>