Maximum Bandwidth Allocation

You are given a set of devices, each with a bandwidth requirement, and several queries each representing an available bandwidth limit. For each query, your task is to determine the maximum total bandwidth that can be allocated to a contiguous prefix of devices (after sorting their bandwidth requirements in non-decreasing order) such that the allocated bandwidth does not exceed the given limit.

More formally, if the sorted bandwidth requirements are \(A_1 \leq A_2 \leq \cdots \leq A_N\) and \(P(k) = \sum_{i=1}^{k} A_i\), then for a given query with limit \(C\), find the maximum \(P(k)\) such that \(P(k) \leq C\). If \(P(N) \leq C\), output \(P(N)\); otherwise, find the largest \(k\) for which \(P(k) \leq C\) using binary search.

This problem requires careful handling of prefix sums and efficient search techniques.

inputFormat

The input is given from stdin in the following format:

T
N Q
A1 A2 ... AN
C1 C2 ... CQ
... (repeated for each test case)

Where:

• T is the number of test cases.
• For each test case, N is the number of devices and Q is the number of queries.
• The next line contains N space-separated integers representing the bandwidth requirements of each device.
• The following line contains Q space-separated integers, each a query representing a bandwidth limit.

outputFormat

For each query, print the maximum total allocated bandwidth on a new line to stdout. If there are multiple test cases, the outputs for all queries should be printed in the order of the test cases.

## sample

1
5 3
1 2 3 4 5
10 15 20

10
15
15

</p>