In this lab, you are tasked with implementing an exhaustive search algorithm to solve the $0-1$

knapsack problem. As you recall $($Chapter $3$ in the textbook$),$ in the $0-1$ knapsack problem items

cannot be broken up so must either all be placed in the knapsack or left out$)$ the objective is to

maximize the total value of the items placed in the knapsack, constrained by the total weight

capacity of the knapsack.

Input

The first line contains an integer n$,$ representing the number of items available to lace in the

knapsack. The second line contains an integer W$,$ representing the total weight capacity of the

knapsack. The third line contains n integers, separated by spaces. These integers represent the

weight of each item. The fourth line contains n integers, separated by spaces. These integers

represent the value of each item.

Output

The output contains $1$ line only, with $1$ integer. The integer represents the total value of the items

placed in the knapsack.

Sample Test Cases

Input Output

$4$

$5$

$2132$

$1210201739$

$5$

$6$

$32145$

$252015405065$