BTCODE_B - Finding Minimum

You are given 'n' integers k1, k2 ... kn and an integer 'x', which satisfy the equation x1k1 * x2k2 * ... * xnkn = x. You are also given values a1, a2 ... an and y1, y2 ... yn. Your task is to find the least positive value 'v', that can be taken by the expression: a1*x1y1 + a2*x2y2 + ... + an*xnyn. Note that x1, x2, x3 ... xn are some variables (not necessarily integers), which can only take positive values.

Input

The first line of input contains a single integer 't', denoting the number of test cases.
The first line of each testcase contains two space separated integers 'n' and 'x'.
Next line contains 'n' integers k1, k2 ... kn.
Next line contains 'n' integers a1, a2 ... an.
Next line contains 'n' integers y1, y2 ... yn.

Output

For each testcase output the least positive value 'v' that can be taken by the expression. To avoid floating point errors, round it off to the nearest integer.

For example, 12.6 is rounded off to 13, and 12.4 is rounded off to 12. To avoid ambiguity, there will be no test case for which the fractional part of the answer equals 0.5.

Example

Input:
2
1 4
2
3
3
2 6
1 1
1 1
1 1

Output:
24
5

Constraints

t <= 25
1 <= n <= 20
1 <= x <= 1000000
1 <= ki, ai, yi <= 20
xi > 0

Explanation

Test case 1: x12 = 4. Therefore, x1 = 2 and 3*x13 = 24.
Test case 2: x1*x2 = 6. Minimum value of x1 + x2 is 2*sqrt(6) = 4.89897. x1 = sqrt(6) and x2 = sqrt(6) gives this solution. Answer is 4.89897, which when rounded off to the nearest integer equals 5.


Added by:suhash
Date:2011-02-26
Time limit:0.405s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India

hide comments
2016-06-13 06:26:51 Piyush Kumar
I am getting WA. I am pretty sure that my solution is correct. Can somebody provide more test cases?
2012-07-18 06:36:50 Bharath Reddy
Olympiad problem...
2011-06-27 18:29:35 i_am_me
my code is giving wrong answer. can anyone give me some typical test case....
2011-03-02 13:26:42 mike_nzk
an MO problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.