Crystal Collection#375
A mineralogy museum is holding an exhibition of rare crystals. In a special room, there are collections, numbered from to . In collection number , there are crystals; each crystal has a weight W_k and a scientific value C_k.
The museum curator wants to select crystals for a new exhibition, but the maximum weight capacity of the exhibition display case is .
Your task is to help the curator select crystals such that their total weight does not exceed and their total scientific value is as large as possible.
The first line contains an integer — the number of test cases. Each test case starts with a line containing two integers and , separated by a space. The next line contains integers W_k, separated by spaces. The following line contains integers C_k, separated by spaces.
For each test case, print a line with the maximal possible total scientific value of the crystals.
Constraints
1 \leq T \leq 74 1 \leq N \leq 15 1 \leq M \leq 1000000000 (10^9) 1 \leq W_k, C_k \leq 1000000000 (10^9)
Example 1