The Robbery

Time limit3sMemory limit128 MB

Summary

Given N item types where type k has exactly k identical copies, pick copies within a weight budget M to maximize total value (bounded knapsack with huge M and small N).

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Greedy
Solved: No attempts yet

Problem

In the downtown of Bucharest there is a very big bank with a very big vault. Inside the vault there are $N$ very big boxes, numbered from 1 to $N$ . Inside the box with number $k$ there are exactly $k$ very big diamonds, and every diamond in that box has weight $W_k$ and cost $C_k$ .

John and Brus are inside the vault at the moment. They would like to steal everything, but unfortunately they are able to carry diamonds with a total weight not exceeding $M$ .

You may take any number of diamonds from box $k$ , from 0 up to all $k$ of them. Your task is to help John and Brus choose diamonds with a total weight less than or equal to $M$ and the maximal possible total cost.

Input

The first line contains a single integer $T$ — the number of test cases. Each test case starts with a line containing two integers $N$ and $M$ separated by a single space. The next line contains $N$ integers $W_k$ separated by single spaces. The following line contains $N$ integers $C_k$ separated by single spaces.

Output

For each test case print a single line containing the maximal possible total cost of the stolen diamonds.

Constraints

$1 \le T \le 74$
$1 \le N \le 15$
$1 \le M \le 10^9$
$1 \le W_k, C_k \le 10^9$

Examples1

Example 1
Input
```
2
2 4
3 2
5 3
3 100
4 7 1
5 9 2
```
Expected output
```
6
29
```