Question
Sum Slice
In a land of numbers, Alice and Ram hold distinct arrays: Alice’s with n elements, Ram’s with m. For each number in Ram’s array, find the length of the longest subsequence from Alice’s array with a sum not exceeding that number.
Compute the maximum subsequence length for each of Ram’s numbers.
Note: A subsequence preserves order but can skip elements.
Input
The first line of the input contains n denoting the length of the Alice’s array.
The second line of the input contains m denoting the length of the Ram's array.
The following line contains the n space-separated integers, representing the elements of the Alice’s array.
The last line contains the m space-separated integers, representing the elements of the Ram's array.
The second line of the input contains m denoting the length of the Ram's array.
The following line contains the n space-separated integers, representing the elements of the Alice’s array.
The last line contains the m space-separated integers, representing the elements of the Ram's array.
Output
Print a space-separated array answer of length m.
Example
Sample Input
4
3
4 5 2 1
3 10 21
Sample Output
2 3 4
Explanation
- The subsequence [2, 1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4, 5, 1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4, 5, 2, 1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.
4
3
4 5 2 1
3 10 21
Sample Output
2 3 4
Explanation
- The subsequence [2, 1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4, 5, 1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4, 5, 2, 1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.