Mind flayer, the shadow monster has attacked the town of Hawkins again. This time, the mind flayer has taken full preparations to fight against El, the girl with psychokinetic abilities. In spite of taking these preparations, he realizes that he can't defeat El at all. So, after observing and analyzing all the circumstances, he has made an alternative plan. He has searched and found an expert problem setter in upside down. The problem setter has set a new problem for him. After that, the mind flayer has given the problem to El saying that if she can not solve the problem within due time, he will destroy the whole town. El is trying the heart & soul to solve the problem. But as she is not a good problem solver, she can not find out the fast solution to the problem. Her code runs for infinite time and gives no output. Jim Hopper, the chief of police of Hawkins has hired you to help El. Now your task is to help El to solve the problem and save the town of Hawkins from the attack of the mind flayer.
The problem given to El is this:
You'll be given two lists A, B, and an integer K. For each integer Bi in B, find the largest number Ag in original list A which is smaller than Bi. If there is no number in original list A which is smaller than Bi, let, Ag = 0. Then append the number (Bi + Ag), K times to the updating list A. The final updated list A is called list C.
For example:
If A = [2, 93, 81], B = [100, 1] and K = 2, after doing all the above operations the list C will be [2, 93, 81, 193, 193, 1, 1].
Let, for an integer Ci in the list C, x is the maximum number of values from B such that the summation of the values is less or equal than Ci. Calculate the x for each and every integer Ci of the list C and print the summation of all x.
Input
Input will start with an integer T, the number of test cases.
In each test case, the first line will contain 3 integers N, M, K - the size of the list A, the size of the list B and the integer K.
The next line will contain N integers, the elements Ai of the list A.
The last line of each test case contains M integers, the elements Bi of the list B.
Constraints:
1 <= T <= 10
1 <= N <= 105
1 <= M <= 105
1 <= K <= 100
1 <= Ai <= 5105
1 <= Bi <= 5105
For 10 points: 1 <= N <= 102, 1 <= M <= 102
For 40 points: 1 <= N <= 5104, 1 <= M <= 2104
For 100 points: 1 <= N <= 105, 1 <= M <= 105
Output
For each test case, print the summation of all x described in the problem statement in a single line.
Sample
| Input | Output |
|---|---|
1 3 2 2 2 93 81 100 1 | 9 |
