Order Splitter
Electronic exchange is a complicated realtime order processing system. Today electronic exchanges operate in the market handling millions of orders every day. You have set up a small company which provides execution services for clients and you're facing a problem of large order splitting between exchanges. It's very competitive to set up a new exchange, hence there is only limited number of exchanges available to split an order 1 ≤ N ≤ 30.
An order has a notional (projected amount that has to be executed on the exchanges) 1 ≤ L ≤ 10^9 and a price. In scope of this problem, you only care about the notional. The price at which an order is sent to an exchange will be provided by a client and forwarded as is to the exchange. The given order has to be split into multiple child orders, which are sent to the exchange, according to the ratios R_i given, for each 0 ≤ i < N. However, each exchange has restrictions on the step size. Each order notional has to be divisible by a certain step size specified by the exchange. You are given a step size of each exchange S_i, meaning that each exchange can only accept orders of notional S_i, 2·S_i, 3·S_i....
Because it's not always possible to split the client order notional precisely into child orders an algorithm has to be written to achieve the best possible allocation that minimizes D=|L-C_i|, where the notionals of the child orders allocated to corresponding exchanges are denoted as C_i. Clients prefer that the child order size is not significantly different to CR_i=L·R_i/R_i. To meet that requirement C_i can be obtained only by rounding CR_i either up or down to the step size. However, if CR_i is divisible by S_i, it's required that C_i = CR_i. It means that you must send the child order notional according to the given ratio if it can be sent, or otherwise round it either up or down. If rounding down yields 0notional, then you can choose not to send an order to the exchange.
Input
The first line of each test case contains 2 integers: number of exchanges 1 ≤ N ≤ 30, the order notional to split 1 ≤ L ≤ 10^9. The second line contains N integers specifying 0 ≤ R_i ≤ 100, R_i > 0. The third line contains N integers specifying the step sizes 1 ≤ S_i ≤ 10^9.
Output
For each test case output one line containing the cumulative notional of the child orders L_r=C_i, optimised according to the rules described above. If there is more than one optimal L_r, output the smaller value.