Limits
1s, 256 MB

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 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 <= 101 <= N <= 1051 <= M <= 1051 <= K <= 1001 <= Ai <= 5**

For each test case, print the summation of all **x** described in the problem statement in a single line.

Input | Output |
---|---|

1 3 2 2 2 93 81 100 1 | 9 |

Login to submit.

76%
Solution Ratio

NirjhorEarliest,

Nafis2003174.132453Fastest, 0.0s

Nafis2003174.132453Lightest, 155 kB

jaberndcShortest, 631B

Toph uses cookies. By continuing you agree to our Cookie Policy.