Chef gave you an infinite number of candies to sell. There are N customers, and the budget of the i^{th} customer is A_{i} rupees, where 1 ≤ A_{i} ≤ M. 

You have to choose a price P, to sell the candies, where 1 ≤ P ≤ M.  
The i^{th} customer will buy exactly \lfloor{\frac{A_{i}}{P}} \rfloor candies.  
Chef informed you that, for each candy you sell, he will reward you with C_{P} 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 - A_{1}, A_{2}, \ldots, A_{N}, the budget of i^{th} person.
- The third line contains M integers - C_{1}, C_{2}, \ldots, C_{M}, 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 ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N, M ≤ 10^{5}$
$1 ≤ A_{i} ≤ M$
$1 ≤ C_{j} ≤ 10^{6}$
- The elements of array $C$ are not necessarily non-decreasing.
- The sum of $N$ and $M$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
2
5 6
3 1 4 1 5
1 4 5 5 8 99
1 2
1
4 1

----- Sample Output 1 ------ 
20
4

----- explanation 1 ------ 
Test case $1$:
- If we choose $P = 1$, the number of candies bought by each person is $[\lfloor{\frac{3}{1}} \rfloor, \lfloor{\frac{1}{1}} \rfloor, \lfloor{\frac{4}{1}} \rfloor, \lfloor{\frac{1}{1}} \rfloor, \lfloor{\frac{5}{1}} \rfloor]$. 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 $[\lfloor{\frac{3}{2}} \rfloor, \lfloor{\frac{1}{2}} \rfloor, \lfloor{\frac{4}{2}} \rfloor, \lfloor{\frac{1}{2}} \rfloor, \lfloor{\frac{5}{2}} \rfloor]$. 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 $[\lfloor{\frac{3}{3}} \rfloor, \lfloor{\frac{1}{3}} \rfloor, \lfloor{\frac{4}{3}} \rfloor, \lfloor{\frac{1}{3}} \rfloor, \lfloor{\frac{5}{3}} \rfloor]$. 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 $[\lfloor{\frac{3}{4}} \rfloor, \lfloor{\frac{1}{4}} \rfloor, \lfloor{\frac{4}{4}} \rfloor, \lfloor{\frac{1}{4}} \rfloor, \lfloor{\frac{5}{4}} \rfloor]$. Thus our bonus is $(0 + 0 + 1 + 0 + 1) \cdot5 = 10$.
- If we choose $P = 5$, the number of candies bought by each person is $[\lfloor{\frac{3}{5}} \rfloor, \lfloor{\frac{1}{5}} \rfloor, \lfloor{\frac{4}{5}} \rfloor, \lfloor{\frac{1}{5}} \rfloor, \lfloor{\frac{5}{5}} \rfloor]$. 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 $[\lfloor{\frac{3}{6}} \rfloor, \lfloor{\frac{1}{6}} \rfloor, \lfloor{\frac{4}{6}} \rfloor, \lfloor{\frac{1}{6}} \rfloor, \lfloor{\frac{5}{6}} \rfloor]$. 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 $[\lfloor{\frac{1}{1}} \rfloor]$. Thus, our bonus is $1 \cdot 4 = 4$.
- If we choose $P = 2$, the number of candies bought by each person is $[\lfloor{\frac{1}{2}} \rfloor]$. Thus, our bonus is $0 \cdot 1 = 0$.

Thus, the answer is $4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Mathematics

Data structures

Range queries


Solutions:
def LII():
	return [int(x) for x in input().split()]
for _ in range(int(input())):
	(n, m) = LII()
	a = LII()
	c = LII()
	hist = [0] * (m + 1)
	for x in a:
		hist[x] += 1
	for i in reversed(range(m)):
		hist[i] += hist[i + 1]
	print(max((c[p - 1] * sum((hist[k * p] for k in range(1, m // p + 1))) for p in range(1, m + 1))))


def LII():
	return [int(x) for x in input().split()]
for _ in range(int(input())):
	(n, m) = LII()
	a = LII()
	assert len(a) == n
	c = LII()
	assert len(c) == m
	assert all((x >= 1 and x <= m for x in a))
	hist = [0] * (m + 1)
	for x in a:
		hist[x] += 1
	for i in range(1, m + 1):
		hist[i] += hist[i - 1]
	print(max((c[p - 1] * (n * (m // p) - sum((hist[k * p - 1] for k in range(1, 1 + m // p)))) for p in range(1, m + 1))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cts = [0] * (m + 1)
	for cu in a:
		cts[cu] += 1
	for i in range(m - 1, 0, -1):
		cts[i] += cts[i + 1]
	best = c[0] * sum(cts)
	for i in range(2, m + 1):
		upd = 0
		for j in range(i, m + 1, i):
			upd += cts[j]
		best = max(best, upd * c[i - 1])
	print(best)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ar = list(map(int, input().split()))
	br = list(map(int, input().split()))
	pref = [0] * (m + 1)
	for i in ar:
		pref[i] += 1
	for i in range(1, m + 1):
		pref[i] += pref[i - 1]
	res = 0
	for i in range(1, m + 1):
		val = 0
		for j in range(i, m + 1, i):
			x = min(m, j + i - 1)
			val += j // i * (pref[x] - pref[j - 1])
		res = max(res, val * br[i - 1])
	print(res)


import heapq
t = int(input())

def check(p, a, c):
	s = 0
	for can in a:
		sold = can // p
		s += sold
	return s * c
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	pref = [0] * (m + 1)
	for x in a:
		pref[x] += 1
	for i in range(1, m + 1):
		pref[i] += pref[i - 1]
	ans = 0
	for x in range(1, m + 1):
		val = 0
		for y in range(x, m + 1, x):
			R = min(m, y + x - 1)
			val += y // x * (pref[R] - pref[y - 1])
		ans = max(ans, val * c[x - 1])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	cur_max = -1
	cur = 0
	pref = [0] * (m + 1)
	for i in a:
		pref[i] += 1
	for i in range(m + 1):
		pref[i] += pref[i - 1]
	for i in range(1, m + 1):
		val = 0
		for j in range(i, m + 1, i):
			val += j // i * (pref[m if m < i + j - 1 else i + j - 1] - pref[j - 1])
		if val * c[i - 1] > cur_max:
			cur_max = val * c[i - 1]
	print(cur_max)


from itertools import accumulate
for t in range(int(input())):
	(n, m) = map(int, input().split())
	arrn = list(map(int, input().split()))
	arrm = list(map(int, input().split()))
	freq = [0] * (m + 1)
	for i in arrn:
		freq[i] += 1
	pref = list(accumulate(freq))
	ans = 0
	for i in range(1, m + 1):
		candies = 0
		for j in range(1, m // i + 1):
			candies += j * (pref[min(i * (j + 1) - 1, m)] - pref[i * j - 1])
		ans = max(ans, candies * arrm[i - 1])
	print(ans)


import math, copy
from sys import stdin
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	nocm = [0] * (m + 1)
	for i in a:
		nocm[i] += 1
	for i in range(m + 1):
		nocm[i] += nocm[i - 1]
	maxval = 0
	for p in range(1, m + 1):
		val = 0
		for i in range(p, m + 1, p):
			val += i // p * (nocm[min(m, i + p - 1)] - nocm[i - 1])
		maxval = max(maxval, val * c[p - 1])
	print(maxval)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	pref = [0] * (m + 1)
	for x in a:
		pref[x] += 1
	for i in range(1, m + 1):
		pref[i] += pref[i - 1]
	ans = 0
	for x in range(1, m + 1):
		val = 0
		for y in range(x, m + 1, x):
			R = min(m, y + x - 1)
			val += y // x * (pref[R] - pref[y - 1])
		ans = max(ans, val * c[x - 1])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	C = list(map(int, input().split()))
	mn = min(C)
	M = list(map(int, input().split()))
	C.sort()
	Lf = [0] * (m + 1)
	for j in range(n):
		Lf[C[j]] += 1
	Lcf = [Lf[0]]
	L = []
	for i in range(1, len(Lf)):
		Lcf.append(Lcf[-1] + Lf[i])
	for i in range(1, m + 1):
		s = 0
		for j in range(i, m + 1, i):
			s += j // i * Lf[j]
			e = (Lcf[j] - Lf[j] - Lcf[j - i]) * ((j - i) // i)
			s += e
			if j + i > m and j != m:
				s += (Lcf[-1] - Lcf[j]) * (j // i)
				continue
		L.append(s * M[i - 1])
	print(max(L))


import sys
from bisect import bisect_left

def main():
	tc = int(input())
	for _ in range(tc):
		(n, m) = map(int, input().split())
		price = [int(a) for a in input().split()]
		bonus = [int(a) for a in input().split()]
		price.sort()
		ans = 0
		for i in range(1, m + 1):
			tot = 0
			for j in range(i, m + 1, i):
				tot += n - bisect_left(price, j)
			ans = max(ans, tot * bonus[i - 1])
		print(ans)
main()


t = int(input())
for i in range(t):
	(n, m) = [int(h) for h in input().split()]
	A = [int(h) for h in input().split()]
	C = [int(h) for h in input().split()]
	freq = [0] * (m + 1)
	cf = [0] * (m + 1)
	cS = [0] * (m + 1)
	for j in A:
		freq[j] += 1
	temp = 0
	for j in range(1, m + 1):
		temp += freq[j]
		cf[j] = temp
	temp = 0
	for j in range(1, m + 1):
		temp += freq[j] * j
		cS[j] = temp
	ans = cS[-1] * C[0]
	for j in range(2, m + 1):
		temp = cS[-1]
		for k in range(0, m + 1, j):
			up = min(k + j - 1, m)
			r = cS[up] - cS[k]
			g = cf[up] - cf[k]
			r -= g * k
			temp -= r
		ans = max(ans, C[j - 1] * (temp // j))
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	freq = [0] * (m + 1)
	for el in arr:
		freq[el] += 1
	for el in range(1, m + 1):
		freq[el] += freq[el - 1]
	ans = 0
	for pr in range(1, m + 1):
		i = 0
		for t in range(1, m // pr + 1):
			e = freq[min(pr * (t + 1) - 1, m)] - freq[min(pr * t - 1, m)]
			i += e * t
		ans = max(ans, i * brr[pr - 1])
	print(ans)


def solve():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	cnt = [0 for i in range(m + 1)]
	for i in a:
		cnt[i] += 1
	for i in range(1, m + 1):
		cnt[i] += cnt[i - 1]
	ans = 0
	for p in range(1, m + 1):
		candies = 0
		for x in range(1, m + 1):
			if x > int(m / p):
				break
			l = x * p - 1
			r = min(m, (x + 1) * p - 1)
			candies += (cnt[r] - cnt[l]) * x
		ans = max(ans, candies * c[p - 1])
	print(ans)
for _ in range(int(input())):
	solve()


import math
test = int(input())
for t in range(test):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	maxi = 0
	store = 0
	indices = []
	for k in range(len(c)):
		if c[k] > store:
			indices.append(k)
			store = c[k]
	i = 0
	while i < len(indices) and i <= max(a):
		sum = 0
		for h in range(len(a)):
			sum += a[h] // (indices[i] + 1)
		maxi = max(maxi, sum * c[indices[i]])
		i += 1
	print(maxi)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def lsi():
	return si().strip().split(' ')

def ni():
	return int(input())
for _ in range(ni()):
	(n, m) = mi()
	a = li()
	c = li()
	pref = [0] * (m + 1)
	for x in a:
		pref[x] += 1
	for i in range(1, m + 1):
		pref[i] += pref[i - 1]
	ans = 0
	for x in range(1, m + 1):
		val = 0
		for y in range(x, m + 1, x):
			R = min(m, y + x - 1)
			val += y // x * (pref[R] - pref[y - 1])
		ans = max(ans, val * c[x - 1])
	print(ans)


t = int(input())
while t:
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	n = 0
	if x > 10 ** 3:
		for u in range(0, y):
			n1 = b[u] // (u + 1) + 1
			if n1 > n:
				a1 = [u1 // (u + 1) for u1 in a]
				a2 = sum(a1) * b[u]
				if a2 > c:
					c = a2
				n = n1
	else:
		for u in range(0, y):
			a1 = [u1 // (u + 1) for u1 in a]
			a2 = sum(a1) * b[u]
			if a2 > c:
				c = a2
	print(c)
	t -= 1


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = defaultdict(int)
	for i in a:
		d[i] += 1
	ans = sum(a) * c[0]
	val = sum(a)
	a = list(set(a))
	a.sort(reverse=True)
	n1 = len(a)
	c1 = max(c)
	c2 = 0
	d1 = defaultdict(int)
	for i in range(2, m + 1):
		if c2 >= c[i - 1]:
			continue
		else:
			c2 = c[i - 1]
		if d1[c[i - 1]] == 1:
			continue
		d1[c[i - 1]] = 1
		j = 0
		s = 0
		while j < n1:
			v = a[j] // i
			if v == 0:
				n1 = j
				break
			s += v * d[a[j]]
			j += 1
		ans = max(ans, s * c[i - 1])
		if n1 == 0 or c1 == c[i - 1] or ans >= c1 * s or (ans >= c1 * val // i):
			break
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	mp = max(a)
	budgets = [0 for i in range(mp + 1)]
	ac = Counter(a)
	for j in range(1, mp + 1):
		if j in ac:
			budgets[j] = budgets[j - 1] + ac[j]
		else:
			budgets[j] = budgets[j - 1]
	prices = [0 for i in range(m)]
	prices[0] = sum(a)
	for i in range(1, m):
		p = i + 1
		for j in range(mp // p + 1):
			if (j + 1) * p - 1 <= mp:
				prices[i] += j * (budgets[(j + 1) * p - 1] - budgets[j * p - 1])
			else:
				prices[i] += j * (budgets[-1] - budgets[j * p - 1])
	for j in range(m):
		prices[j] = prices[j] * c[j]
	print(max(prices))


T = int(input())
for i in range(T):
	(N, M) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	C = [int(x) for x in input().split()]
	max_C = 0
	max_bonus = 0
	for j in range(M):
		number_of_candies = 0
		if C[j] > max_C and C[j] / (j + 1) >= max_C / (j + 1):
			max_C = C[j]
			for k in range(N):
				number_of_candies += A[k] // (j + 1)
			if number_of_candies * C[j] > max_bonus:
				max_bonus = number_of_candies * C[j]
	print(max_bonus)


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
tc = int(input())
for test_cases in range(1, tc + 1):
	(n, m) = inp()
	a = inp()
	c = inp()
	m_ = m
	m = 2 * m
	arr = [0] * (m + 1)
	for i in a:
		arr[i] += 1
	pre = [0] * (m + 1)
	for i in range(1, m + 1):
		pre[i] += pre[i - 1] + arr[i]
	ans = 0
	for i in range(1, m_ + 1):
		res = 0
		cnt = 0
		mul = 0
		for j in range(i + i - 1, m + 1, i):
			res += (pre[j] - pre[j - i]) * (j // i)
		ans = max(ans, res * c[i - 1])
	print(ans)