AUT  Vending Machine
Byteasar studies computer science at the University of Bytetown. There is a snack vending machine at his faculty that sells n types of snacks, numbered 1 through n Snacks of different types may have different price, since they differ in size and flavor.
Recently Byteasar discovered that the vending machine is broken. If one buys a snack of type i, the vending machine additionally dispenses one snack of each of the types 1, 2, ..., i1, provided that snacks of these types are available (if there are no snacks of some of the types 1, 2, ..., i1, simply no snack of this type is dispensed). Buying snack of type i is possible only if at least one snack of this type is available.
Byteasar decided to take advantage of the fault he discovered. He would like to find out what is the maximum total value (that is, the sum of prices) of snacks that he can obtain in the vending machine using a given amount of money. He does not have to use all the money.
Input
First line contains a single integer t representing the number of test cases to be solved. The description of t test cases follows.
The first line of each test case contains two integers n and k (1 <= n <= 40, 1 <= k <= 64000): the number of types of snacks and the amount of money that Byteasar has at his disposal. The second line holds n integers c_{1}, ..., c_{n} (1 <= c_{i} <= 40), the prices of snacks of respective types. The third line holds n integers l_{1}, ..., l_{n} (1 <= l_{i} <= 40), the quantities of snacks of respective types that are available in the vending machine.
Output
The output should contain one integer per test case: the total price of snacks that Byteasar can obtain in the vending machine using at most k units of money.
Example
Input:16 8 7 2 3 5 7 2 1 3 0 3 2 1Output:
30
Task author: Jakub Pachocki
hide comments
hodobox:
20170807 17:54:16
I don't want to spoil, but here's a hint: if other constraints remain the same, it does not matter at all whether the limit is k<=2000, k<=64000 or k<=10^18 :) 

Rishav Goyal:
20150816 20:35:30
time limit is strict or the optimal solution is very hard to implement :( .


acheron:
20130923 20:09:16
The cluster was changed to Pentium III. The previous cluster had a high memory limit. All submissions were rejudged, I apologize for the inconvenience. 

Raja CSE:
20130923 19:17:29
pls give some clue

Added by:  acheron 
Date:  20130904 
Time limit:  0.739s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  AMPPZ 2012 