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 \textbf{1} ≤ \textbf{N} ≤ \textbf{30}. An order has a notional (projected amount that has to be executed on the exchanges) \textbf{1} ≤ \textbf{L} ≤ \textbf{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 \textbf{R_i} given, for each \textbf{0} ≤ \textbf{i} < \textbf{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 \textbf{S_i}, meaning that each exchange can only accept orders of notional \textbf{S_i}, \textbf{2·S_i}, \textbf{3·S_i}.... \includegraphics{https://static.e-olymp.com/content/e7/e74d54278784e28fb95028ce0b789b99745a4d4f.jpg} \includegraphics{file:///E:/2012-2013/ACM/BSU-2012/problems/splitter/statements/.html/russian/9d7c9f5e6b7b1a23a4b9b716012f8270961d1a04.png} \includegraphics{file:///E:/2012-2013/ACM/BSU-2012/problems/splitter/statements/.html/russian/cd7fc5d7309047c2ee033d6e07307ee632bdfe5b.png} \includegraphics{https://static.e-olymp.com/content/e7/e74d54278784e28fb95028ce0b789b99745a4d4f.jpg} 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 \textbf{D=|L-C_i|}, where the notionals of the child orders allocated to corresponding exchanges are denoted as \textbf{C_i}. Clients prefer that the child order size is not significantly different to \textbf{CR_i=L·R_i/R_i}. To meet that requirement \textbf{C_i} can be obtained only by rounding \textbf{CR_i} either up or down to the step size. However, if \textbf{CR_i} is divisible by \textbf{S_i}, it's required that \textbf{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 \textbf{0}notional, then you can choose not to send an order to the exchange. \InputFile \includegraphics{https://static.e-olymp.com/content/e7/e74d54278784e28fb95028ce0b789b99745a4d4f.jpg} \includegraphics{file:///E:/2012-2013/ACM/BSU-2012/problems/splitter/statements/.html/russian/23b62ca648ccc566e6109f087b860f581246e958.png} The first line of each test case contains \textbf{2} integers: number of exchanges \textbf{1} ≤ \textbf{N} ≤ \textbf{30}, the order notional to split \textbf{1} ≤ \textbf{L} ≤ \textbf{10^9}. The second line contains \textbf{N} integers specifying \textbf{0} ≤ \textbf{R_i} ≤ \textbf{100}, \textbf{R_i} > \textbf{0}. The third line contains \textbf{N} integers specifying the step sizes \textbf{1} ≤ \textbf{S_i} ≤ \textbf{10^9}. \OutputFile \includegraphics{file:///E:/2012-2013/ACM/BSU-2012/problems/splitter/statements/.html/russian/ae9ce0ab7a4bc3f79bf44a07c3fb44cf9d8e3b3f.png} \includegraphics{https://static.e-olymp.com/content/e7/e74d54278784e28fb95028ce0b789b99745a4d4f.jpg} For each test case output one line containing the cumulative notional of the child orders \textbf{L_r=C_i}, optimised according to the rules described above. If there is more than one optimal \textbf{L_r}, output the smaller value.