Bob has N workers working under him. The i^th worker has some strength W_i. Currently, he has M tasks pending with him. Each task can be assigned to only 1 worker. To do particular task i, Strength S_i is required i.e. a task i can be done by a worker only if his strength is greater or equal to S_i. Bob has K magical pills, taking a magical pill will increase the strength of a worker by B units. Bob gives pills to workers optimally such that the maximum number of tasks can be done.

Task
Determine the maximum number of tasks that can be completed.

Note: 1-based indexing is followed.

Example

Assumptions

• K = 10
• B = 1
• N = 3
• W = [10, 5, 4] 
• M = 3
• S = [ 15, 4, 20]

Approach

There are many ways to assign workers to different tasks, some of the ways are:

• Bob can assign task 2 to worker 2 and he can give 5 pills to worker 1 which will increase his strength to 15 and then assign task 1 to him. So at max 2 tasks can be completed. There is no way in which he can get more than 2 tasks done. 
• Alternatively, he can give 10 pills to worker 3 and assign him task 3, and assign worker 1 to task 2.
• Therefore, the maximum number of tasks that can be assigned is 2.

Function description

Complete the solve function provided in the editor. This function takes the following 6 parameters and returns an integer:

• K: Represents the number of magical pills
• B: Represents an integer denoting the amount of strength that will be increased by taking a pill
• N: Represents the number of workers
• W: Represents an array of integers denoting the strength of the workers
• M: Represents the number of tasks
• S: Represents an array of integers denoting strength required for the task

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains an integer T denoting the number of test cases. T also denotes the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line contains two space-separated integers K and B.
  • The second line contains an integer N denoting the number of workers.
  • The third line contains N space-separated integers denoting an array W where W[i] represents the strength of the i^th worker.
  • The fourth line contains an integer M denoting the number of tasks.
  • The fifth line contains M space-separated integers denoting an array S. S[i] represents the strength required to do the i^th task.

Output format

For each test case in a new line, print the answer representing the maximum number of tasks that can be done.

Constraints

\(1 \le T \le 100\)
\(1 \le K \le 10^5\)
\(1 \le B \le 10\)
\(1 \le N,M \le 10^4\)
\(1 \le W[i],S[i] \le 10^5\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.