401. 0-1 Knapsack

0

Medium

You are preparing for a seaside vacation and can only bring one bag with a capacity of S (1 <= S <= 1000).
You have N (1 <= N <= 1000) items that you may want to bring with you.
However, not all items can fit in the bag, so you must choose.
Each item has a size and a value.
Your goal is to maximize the total value of the items you bring.
What is the maximum total value you can achieve?

Input Format

The first line contains two integers, N and S, separated by a space.

The second line contains N space-separated integers, representing the sizes of the items.

The third line contains N space-separated integers, representing the values of the items.

The second line contains N space-separated integers, representing the sizes of the items.

The third line contains N space-separated integers, representing the values of the items.

Output Format

Output a single integer representing the maximum value that can be obtained by optimally choosing the items.

Example

Input

5 4
1 2 3 2 2
8 4 0 5 3

Output

13

Constraints

1 <= S,N <= 1000

Loading...

View Submissions

Console