Chef and Stones

All submissions for this problem are available.
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
Example
Input: 1 3 10 3 4 5 4 4 5 Output: 12
Explanation
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.
Author:  berezin 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/CHEFSTON 
Tags  basicmath, berezin, cakewalk, jan15 
Date Added:  1112014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 