Fundraised

Dalia won a prize of X, and now the money has to be spent. Mohamed Fouad, the deputy regional contest director, wants to spend it but cannot decide what to buy. There are N kinds of items he can buy: name tags, T-shirts, helium balloons, trophies, and so on. Each kind has its own importance value and its own price per unit. He can buy as many units of any kind as he wants, as long as the total price stays within the budget.

Find the largest total importance value Fouad can reach by choosing what to buy without going over the budget.

The first line contains an integer T, the number of test cases.

The first line of each test case contains two integers N ($1 \le N \le 100$) and X ($1 \le X \le 10000$), the number of item kinds and the budget. The second line contains N integers $I_0, I_1, \dots, I_{N-1}$ ($1 \le I_i \le 400000$) separated by spaces, where $I_i$ is the importance value Fouad earns from one unit of item i ($0 \le i < N$). The third line contains N integers $C_0, C_1, \dots, C_{N-1}$ ($1 \le C_i \le 1000$) in the same format, where $C_i$ is the price of one unit of item i.

For each test case, print the maximum total importance value Fouad can get on its own line.