Pku3900 The Robbery

内存限制：64 MiB 时间限制：5 Sec

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 k very big diamonds, each of weight Wk and cost Ck.
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 the total weight not exceeding M.
Your task is to help John and Brus to choose diamonds with the total weight less than or
equal to M and the maximal possible total cost.

给出N（N<=15）种物品，其中第I种物品有I个。每个物品有一定的重量和权值。现在给出一个大小为M（M<=10^9）的背包，求出最多能够背走的权值。

The first line contains 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 Wk separated by single spaces. The following line contains N integers Ck separated by single spaces.

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

样例输入

样例输出


			6 

29

Hint



Constraints: 

1 ≤ T ≤ 74, 

1 ≤ N ≤ 15, 

1 ≤ M ≤ 1000000000 (10^9), 

1 ≤ Wk, Ck ≤ 1000000000 (10^9).

#2247. Pku3900 The Robbery

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示