9352번 - Fundraised 다국어

문제

Guess what?! Dalia won the money (an amount X), and now it’s time to spend it. Mohamed Fouad is the deputy regional contest director and he wants to spend the money but he doesn’t know what to spend it on. There are N items that he can buy like name-tags, T-shirts, helium balloons, trophies, etc. each having a different importance value and a cost to buy one unit from (you can buy as much units of any item as you want as long as you don't exceed the budget).

Mohamed wants your help; tell him the maximum importance value he can get after he chooses optimally to buy any number of items without exceeding his budget.

입력

The first line of input contains an integer T, the number of test cases. T test cases follow, the first line of each test case contains two integers (1 ≤ N ≤ 100), (1 ≤ X ≤ 10000). The second line of the test case contains N space separated integers I_i (1 ≤ I_i ≤ 400000), each representing the importance value Fouad earns from item i (0 ≤ i < N). The following line contains N space separated integers C_i (1 ≤ C_i ≤ 1000), each representing the cost of an item i (0 ≤ i < N).

출력

For each test case, on a separate line, output the maximum importance value Fouad can get.

제한

힌트