CPS $340-$ Lab $3(20$pts$)$

Due: Thursday, Jan. $25,2024,$ at $11$:$59$pm via Blackboard

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

$4$

$5$

$2132$

$12102017$

$39$

$5$

$6$

$32145$

$2520154050$

$65$

Output

$132$

$39$

$6$