Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The Robbery
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 2087Accepted: 244

Description

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.

Input

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.

Output

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

Sample Input

2 
2 4 
3 2 
5 3 
3 100 
4 7 1 
5 9 2

Sample Output

6 
29

Hint

Constraints:
1 ≤ T ≤ 74,
1 ≤ N ≤ 15,
1 ≤ M ≤ 1000000000 (109),
1 ≤ Wk, Ck ≤ 1000000000 (109).

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator