Hide

# Problem HMaximum Loot

A burglar wants to maximize the value of his loot given that he has a limited carrying capacity. Which items should he choose?

More precisely, there is for every item $i$ a value $v_{i}$ and a cost (or weight) $c_{i}$, and there is a maximum cost $C$. The object is to find a set $S$ such that $\sum _{i \in S} v_ i$ is maximal while $\sum _{i \in S} c_ i \le C$.

Furthermore, if the burglar breaks into a sweet shop, there will be a lot of items, but they wonâ€™t be very valuable. On the other hand, an art exhibition tends to have few, but very valuable objects. Careful field research has shown that the trade-off between total value $V$ (the sum of all values) and number of items is captured by the inequality $n + 2 \log _{2} V \le 75$.

## Input

The first line contains an integer $1 \le T \le 20$ which is the number of test cases. Each test case consist of three lines. The first line contains the positive integer $n, 1 \le n \le 60$ and the integer capacity $1 \le C \le 2\, 000\, 000\, 000$. The next two lines consist of $n$ space-separated positive integers each, the first being the values $v_{1}, v_2, \ldots , v_ n$, and the second the costs $c_1, c_2, \ldots , c_ n$.

For the purposes of this problem, all input parameters are positive integers and the sum of all values is at most $2\, 000\, 000\, 000$. The sum of all weights is also at most $2\, 000\, 000\, 000$.

## Output

For each test case, print the maximum value the loot can have given the cost constraint. Each test case should produce a single line of output.

## Explanation of Sample Data

In the first case, pick items number 2, 3, and 4 for a total weight of 5, and in the second case pick items number 2, 4, 9 for a total weight of 5.

Sample Input 1 Sample Output 1
2
4 6
5 2 4 1
6 2 1 2
10 5
1 3 2 3 1 1 3 2 4 2
1 2 2 1 1 2 3 1 2 2

7
10

Hide