Read problems statements in Mandarin Chinese  and Russian. 

Chef is playing a game. Currently in the game, he is at a field full of stones. There are total N kinds of 
stones. There is unlimited supply of each kind of stone.  

Chef knows that one stone of kind i needs A_{i} minutes to pick it from the ground and it will give Chef a profit of 
B_{i} Rs. 
Chef has K minutes of free time. During this free time, Chef want to pick stones so as to maximize his profit. 
But he can not pick stones of different kinds, he has to pick stones of a single kind.

Please help Chef to find the maximal possible profit. 

------ Input ------ 

First line contains single integer T denoting the number of test cases. 
First line of each test case contains two integers N and K. 
Next line contains N integers A_{i} denoting the time needed to pick one stone of kind i. 
Next line contains N integers B_{i} denoting the profit due to picking i^{th}th stone. 

------ Output ------ 

For each test case, print a single line containing maximal possible profit. 

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{9}$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$

------ Subtasks ------ 

$Subtask N ≤ 5, T ≤ 2 Points: 30 $
$Subtask N ≤ 10^{5}, T ≤ 5 Points: 70 $
 
----- Sample Input 1 ------ 
1
3 10
3 4 5
4 4 5
----- Sample Output 1 ------ 
12
----- explanation 1 ------ 

If Chef picks stones of first kind he can pick 3 stones, he will get a profit of 3*4 = 12 Rs. 
If Chef picks stones of second kind he can pick 2 stones, he will get a profit of 2*4 = 8 Rs. 
If Chef picks stones of third kind he can pick 2 stones, he will get a profit of 2*5 = 10 Rs. 

So the maximum possible profit is 12.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(stones, profit, maxprofit) = (0, 0, 0)
	for i in range(n):
		stones = k // a[i]
		profit = b[i] * stones
		if profit > maxprofit:
			maxprofit = profit
	print(maxprofit)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	tim = list(map(int, input().split()))
	prof = list(map(int, input().split()))
	ans = 0
	for (i, j) in zip(tim, prof):
		ans = max(ans, k // i * j)
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	time = list(map(int, input().split()))
	value = list(map(int, input().split()))
	profit = -1
	for (t, v) in zip(time, value):
		profit = max(v * (K // t), profit)
	print(profit)


for _ in range(int(input())):
	K = int(input().split()[1])
	print(max([K // int(a) * int(b) for (a, b) in zip(input().split(), input().split())]))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l3 = []
	ma = 0
	for x in l1:
		l3.append(int(k / x))
	for (x, y) in zip(l3, l2):
		m = x * y
		if m > ma:
			ma = m
	print(ma)


from sys import stdin

def main():
	T = int(stdin.readline().strip())
	for _ in range(T):
		(N, K) = map(int, stdin.readline().strip().split())
		times = list(map(int, stdin.readline().strip().split()))
		gains = list(map(int, stdin.readline().strip().split()))
		tablo = [0] * N
		for loop in range(N):
			tablo[loop] = K // times[loop] * gains[loop]
		print(max(tablo))
main()


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = list(map(int, input().split()))
	x = []
	for i in range(n):
		x.append(k // l[i] * s[i])
	print(max(x))


a = int(input(''))
for i in range(a):
	(N, K) = [int(x) for x in input('').split()]
	l = []
	T1 = [int(x) for x in input('').split()]
	T2 = [int(x) for x in input('').split()]
	k1 = list(T1)
	k2 = list(T2)
	for j in range(N):
		f = K // k1[j] * k2[j]
		l.append(f)
	print(max(l))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(k // a[i] * b[i])
	print(max(l))


t = input()
for c in range(0, int(t)):
	(n, k) = input().split()
	a = input().split()
	b = input().split()
	arr = []
	brr = []
	for x in a:
		arr.append(int(x))
	for y in b:
		brr.append(int(y))
	profits = []
	for z in range(0, int(n)):
		profits.append(int(k) // arr[z] * brr[z])
	print(max(profits))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	time = list(map(int, input().split()))
	pric = list(map(int, input().split()))
	profit = []
	for i in range(n):
		a = k // time[i]
		profit.append(a * pric[i])
	print(max(profit))


for t in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	max_profit = 0
	for i in range(N):
		max_profit = max(max_profit, K // A[i] * B[i])
	print(max_profit)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l = [k // l1[i] * l2[i] for i in range(n)]
	print(max(l))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	array_time = list(map(int, input().split()))
	array_price = list(map(int, input().split()))
	count = array_price[0] * (k // array_time[0])
	for i in range(1, n):
		if count <= array_price[i] * (k // array_time[i]):
			count = array_price[i] * (k // array_time[i])
	print(count)
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	l = []
	for i in range(len(A)):
		s1 = k // A[i] * B[i]
		l.append(s1)
	print(max(l))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	p = 0
	for j in range(a):
		v = b // c[j] * d[j]
		if p < v:
			p = v
	print(p)


t = int(input())
while t:
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	mx = 0
	for i in range(n):
		m = k // a[i] * b[i]
		mx = max(m, mx)
	print(mx)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	ans = []
	for x in range(n):
		ans.append(arr2[x] * int(k / arr1[x]))
	print(max(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	minute = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	j = []
	for i in range(n):
		z = k // minute[i] * cost[i]
		j.append(z)
	print(max(j))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = []
	for i in range(n):
		c.append(k // a[i] * b[i])
	print(max(c))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	dic = {a[i]: b[i] for i in range(n)}
	max = 0
	for (key, values) in dic.items():
		m = k // key * values
		if m > max:
			max = m
	print(max)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	p = list(map(int, input().split()))
	for x in range(len(c)):
		c[x] = k // c[x]
	for m in range(len(p)):
		p[m] = p[m] * c[m]
	print(max(p))


t = int(input())
for k in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if int(k / a[i]) * b[i] > c:
			c = int(k / a[i]) * b[i]
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = max(ans, k // a[i] * b[i])
	print(ans)


for _ in range(int(input())):
	(kinds, time) = map(int, input().split())
	timeToPickOne = [int(x) for x in input().split()]
	profitPerStone = [int(x) for x in input().split()]
	num = []
	for i in range(kinds):
		num.append(time // timeToPickOne[i] * profitPerStone[i])
	num.sort()
	print(num[-1])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	s = 0
	for i in range(len(A)):
		s1 = k // A[i] * B[i]
		if s1 > s:
			s = s1
	print(s)


for M in range(int(input())):
	(x, y) = map(int, input().split())
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	l = []
	for i in range(x):
		l.append(y // a1[i] * a2[i])
	print(max(l))


t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	profit = []
	for i in range(N):
		q = K // A[i]
		profit.append(q * B[i])
	print(max(profit))


testcase = int(input())
for i in range(testcase):
	(n, k) = map(int, input().split())
	lstA = list(map(int, input().split()))
	lstB = list(map(int, input().split()))
	lstAB = [lstB[j] * (k // lstA[j]) for j in range(n)]
	print(max(lstAB))


bc = int(input())
for i in range(bc):
	(n, k) = map(int, input().split())
	time = [int(i) for i in input().split()]
	profit = [int(j) for j in input().split()]
	l = []
	m = []
	for i in time:
		l.append(k // i)
	for i in range(n):
		m.append(l[i] * profit[i])
	print(max(m))


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = list(map(int, input().split()))
	m = 0
	for j in range(n):
		pr = k // a[j] * p[j]
		if pr > m:
			m = pr
	print(m)
	t -= 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = []
	for i in range(len(a)):
		d.append(c[i] * (k // a[i]))
	print(max(d))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = 0
	for i in range(n):
		if k // a[i] * b[i] > p:
			p = k // a[i] * b[i]
	print(p)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	l = []
	m = []
	for i in a:
		l.append(int(math.floor(k / i)))
	for j in range(n):
		m.append(l[j] * b[j])
	print(max(m))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	c = 0
	for i in range(n):
		if int(k / a[i]) * l[i] > c:
			c = int(k / a[i]) * l[i]
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(k // t[i] * p[i])
	print(max(l))


for T in range(int(input())):
	l = list(map(lambda x: int(x), input().split()))
	(N, K) = (l[0], l[1])
	A = list(map(lambda x: int(x), input().split()))
	B = list(map(lambda x: int(x), input().split()))
	prof = 0
	for i in range(N):
		if K // A[i] * B[i] > prof:
			prof = K // A[i] * B[i]
	print(prof)


for i in range(int(input())):
	(N, K) = [int(ii) for ii in input().split()]
	T = [int(x) for x in input().split()]
	P = [int(y) for y in input().split()]
	MP = 0
	for ii in range(N):
		MP = max(MP, K // T[ii] * P[ii])
	print(MP)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for i in range(len(b)):
		s = max(s, b[i] * (k // a[i]))
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maxi = 0
	for i in range(n):
		d = k // a[i]
		val = d * b[i]
		maxi = max(val, maxi)
	print(maxi)


casos = int(input())
for i in range(casos):
	(tipo_piedras, minutos_totales) = map(int, input().split())
	minutos_piedras = list(map(int, input().split()))
	valor_piedras = list(map(int, input().split()))
	ganancia = []
	for i in range(tipo_piedras):
		ganancia.append(valor_piedras[i] * (minutos_totales // minutos_piedras[i]))
	print(max(ganancia))


def solve(n, k, a, b):
	ans = 0
	for (i, j) in zip(a, b):
		ans = max(ans, k // i * j)
	print(ans)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	solve(n, k, a, b)


bc = int(input())
for i in range(bc):
	(n, k) = map(int, input().split())
	time = [int(i) for i in input().split()]
	profit = [int(j) for j in input().split()]
	ans = 0
	for (i, j) in zip(time, profit):
		ans = max(ans, k // i * j)
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	profitMax = 0
	for i in range(N):
		pick = K // A[i]
		if pick * B[i] > profitMax:
			profitMax = pick * B[i]
	print(profitMax)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	profit = 0
	for i in range(n):
		if k // a[i] * b[i] > profit:
			profit = k // a[i] * b[i]
	print(profit)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	l2 = []
	for i in range(n):
		m = k // l[i]
		m1 = m * l1[i]
		l2.append(m1)
	print(max(l2))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	max_amt = 0
	for i in range(0, n):
		if arr1[i] <= k:
			stones = k // arr1[i]
			amt = arr2[i] * stones
			if max_amt < amt:
				max_amt = amt
	print(max_amt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = list(map(int, input().split()))
	g = []
	for i in range(len(a)):
		g.append(c[i] * (k // a[i]))
	print(max(g))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append(m // a[i] * b[i])
	print(max(c))


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	d = []
	for i in range(len(A)):
		d.append(k // A[i] * B[i])
	print(max(d))


t = int(input(''))
if t <= 5:
	for _ in range(t):
		flag = 0
		(n, k) = map(int, input().split())
		a = input().split()
		b = input().split()
		c = []
		if 1 <= n <= 10 ** 5 and 1 <= k <= 10 ** 9 and (len(a) == n) and (len(b) == n):
			for i in range(n):
				a[i] = int(a[i])
				b[i] = int(b[i])
				if 1 <= a[i] <= 10 ** 9 and 1 <= b[i] <= 10 ** 9:
					c.append(k // a[i] * b[i])
				else:
					flag = 1
			if flag == 0:
				print(max(c))


f1 = int(input())
for i in range(f1):
	(f2, f3) = map(int, input().split())
	f4 = list(map(int, input().split()))
	f5 = list(map(int, input().split()))
	amt = 0
	for j in range(f2):
		max_amt = f3 // f4[j] * f5[j]
		if max_amt > amt:
			amt = max_amt
	print(amt)


T = int(input())
for i in range(T):
	(a, k) = map(int, input().split())
	stones = list(map(int, input().split()))
	profit = list(map(int, input().split()))
	ip = []
	for z in tuple(zip(stones, profit)):
		ip.append(k // z[0] * z[1])
	print(max(ip))


for i in range(int(input())):
	(n, t) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.insert(i, t // a[i])
	d = []
	for i in range(n):
		d.insert(i, c[i] * b[i])
	max = d[0]
	for i in range(n):
		if max < d[i]:
			max = d[i]
	print(max)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	time = list(map(int, input().split()))
	profit = list(map(int, input().split()))
	maxi = 0
	for i in range(n):
		temp = k // time[i] * profit[i]
		if temp > maxi:
			maxi = temp
	print(maxi)


try:
	for i in range(int(input())):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		m = 0
		for i in range(n):
			z = k // a[i]
			m = max(m, z * b[i])
		print(m)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()][:n]
	b = [int(i) for i in input().split()][:n]
	c = 0
	l = []
	for i in a:
		x = k // i
		y = b[c] * x
		c += 1
		l.append(y)
	print(max(l))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = -1111111
	for i in range(n):
		x = k // a[i]
		y = b[i] * x
		m = max(m, y)
	print(m)


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	time_arr = list(map(int, input().split()))
	profit_arr = list(map(int, input().split()))
	ans = 0
	for x in range(n):
		ans = max(ans, k // time_arr[x] * profit_arr[x])
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	res = []
	for i in range(n):
		x = k // a[i]
		y = x * b[i]
		res.append(y)
	print(max(res))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append([b[i], a[i]])
	c.sort(key=lambda x: x[0] / x[1], reverse=True)
	i = 0
	s = 0
	while k != 0 and i < n:
		if k >= c[i][1]:
			s = max(s, c[i][0] * (k // c[i][1]))
		i += 1
	print(s)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for j in range(len(a)):
		l.append(b[j] * (k // a[j]))
	print(max(l))


test = int(input())
for _ in range(test):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	maximum = 0
	j = 0
	for i in range(len(b)):
		times = a[1] // b[i]
		profit = times * c[j]
		j = j + 1
		if profit > maximum:
			maximum = profit
	print(maximum)


T = int(input())
while T > 0:
	(N, K) = map(int, input().split(' '))
	A = list(map(int, input().strip().split()))[:N]
	B = list(map(int, input().strip().split()))[:N]
	L = []
	for i in range(N):
		L.append(K // A[i] * B[i])
	L = sorted(L)
	print(L[N - 1])
	T -= 1


t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = list(map(int, input().split()))
	max_profit = 0
	for i in range(n):
		n_stones = k // a[i]
		max_profit = max(max_profit, n_stones * b[i])
	print(max_profit)


t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	arr_A = list(map(int, input().split()))
	arr_B = list(map(int, input().split()))
	maxprofit = 0
	i = 0
	temp = 0
	while i < N:
		temp = K // arr_A[i]
		maxprofit = max(maxprofit, temp * arr_B[i])
		i = i + 1
	print(maxprofit)