#K82572. Max Items Carried
Max Items Carried
Max Items Carried
You are given several test cases. In each test case, there are N people and M items. Each person has a weight limit and each item has a weight. A person can carry an item if and only if the weight of the item does not exceed the person’s weight limit. Each person may carry at most one item, and an item can be carried by at most one person.
Your task is to determine the maximum number of items that can be carried if the items are assigned optimally. Formally, let the weight limits be \(l_1, l_2, \dots, l_N\) and the item weights be \(w_1, w_2, \dots, w_M\). You need to count the maximum number of pairs \((l_i, w_j)\) such that \(w_j \leq l_i\), with each \(l_i\) and \(w_j\) used at most once.
It is advised to solve this problem using a greedy approach. Sort the weight limits and item weights in non-decreasing order and then use a two-pointer strategy to assign items to persons.
inputFormat
The first line of input contains an integer T (\(T \geq 1\)), the number of test cases.
Each test case begins with a line containing two integers N and M representing the number of people and the number of items respectively.
The following line contains N integers indicating the weight limits of the people.
The next line contains M integers indicating the weights of the items.
Input is provided via standard input (stdin).
outputFormat
For each test case, output a single line containing one integer: the maximum number of items that can be carried by the people under the given constraints.
Output should be written to standard output (stdout). Each test case result should be printed on a new line.
## sample2
3 5
10 15 20
5 7 8 9 10
2 4
5 5
3 4 5 3
3
2
</p>