Candies Codechef Solution

Problem

Chef gave you an infinite number of candies to sell. There are $N$ customers, and the budget of the ��ℎith customer is ��Ai​ rupees, where 1≤��≤�1≤Ai​≤M.

You have to choose a price $P$, to sell the candies, where $1\le P\le M$.
The ��ℎith customer will buy exactly ⌊���⌋⌊PAi​​⌋ candies.
Chef informed you that, for each candy you sell, he will reward you with ��CP​ rupees, as a bonus. Find the maximum amount of bonus you can get.

Note:

• We are not interested in the profit from selling the candies (as it goes to Chef), but only the amount of bonus. Refer the samples and their explanations for better understanding.
• $\lfloor x\rfloor$ denotes the largest integer which is not greater than $x$. For example, $\lfloor 2.75\rfloor =2$ and $\lfloor 4\rfloor =4$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $M$, the number of customers and the upper limit on budget/price.
  • The second line contains $N$ integers – �1,�2,…,��A1​,A2​,…,AN​, the budget of ��ℎith person.
  • The third line contains $M$ integers – �1,�2,…,��C1​,C2​,…,CM​, the bonus you get per candy, if you set the price as $i$.

Output Format

For each test case, output on a new line, the maximum amount of bonus you can get.

Constraints

Sample 1:

2
5 6
3 1 4 1 5
1 4 5 5 8 99
1 2
1
4 1

20
4

Explanation:

Test case $1$:

• If we choose $P=1$, the number of candies bought by each person is [⌊31⌋,⌊11⌋,⌊41⌋,⌊11⌋,⌊51⌋][⌊13​⌋,⌊11​⌋,⌊14​⌋,⌊11​⌋,⌊15​⌋]. Thus, our bonus is $(3+1+4+1+5)\cdot 1=14$.
• If we choose $P=2$, the number of candies bought by each person is [⌊32⌋,⌊12⌋,⌊42⌋,⌊12⌋,⌊52⌋][⌊23​⌋,⌊21​⌋,⌊24​⌋,⌊21​⌋,⌊25​⌋]. Thus our bonus is $(1+0+2+0+2)\cdot 4=20$.
• If we choose $P=3$, the number of candies bought by each person is [⌊33⌋,⌊13⌋,⌊43⌋,⌊13⌋,⌊53⌋][⌊33​⌋,⌊31​⌋,⌊34​⌋,⌊31​⌋,⌊35​⌋]. Thus our bonus is $(1+0+1+0+1)\cdot 5=15$.
• If we choose $P=4$, the number of candies bought by each person is [⌊34⌋,⌊14⌋,⌊44⌋,⌊14⌋,⌊54⌋][⌊43​⌋,⌊41​⌋,⌊44​⌋,⌊41​⌋,⌊45​⌋]. Thus our bonus is $(0+0+1+0+1)\cdot 5=10$.
• If we choose $P=5$, the number of candies bought by each person is [⌊35⌋,⌊15⌋,⌊45⌋,⌊15⌋,⌊55⌋][⌊53​⌋,⌊51​⌋,⌊54​⌋,⌊51​⌋,⌊55​⌋]. Thus our bonus is $(0+0+0+0+1)\cdot 8=8$.
• If we choose $P=6$, the number of candies bought by each person is [⌊36⌋,⌊16⌋,⌊46⌋,⌊16⌋,⌊56⌋][⌊63​⌋,⌊61​⌋,⌊64​⌋,⌊61​⌋,⌊65​⌋]. Thus our bonus is $(0+0+0+0+0)\cdot 99=0$.

Thus, the answer is $20$.

Test case $2$:

• If we choose $P=1$, the number of candies bought by each person is [⌊11⌋][⌊11​⌋]. Thus, our bonus is $1\cdot 4=4$.
• If we choose $P=2$, the number of candies bought by each person is [⌊12⌋][⌊21​⌋]. Thus, our bonus is $0\cdot 1=0$.

Thus, the answer is $4$.