Maximizing Souvenir Value

You are given a set of souvenirs, where each souvenir i has a weight \(w_i\) and a value \(v_i\). You have a backpack that can carry at most a weight \(W\). Your task is to choose a subset of the souvenirs such that their total weight does not exceed \(W\) and their total value is maximized.

The problem can be modeled using dynamic programming with the recurrence:

[ \text{dp}[i][w] = \max\big(\text{dp}[i-1][w],, v_i + \text{dp}[i-1][w-w_i]\big) \quad \text{for } w_i \le w, ]

and

[ \text{dp}[i][w] = \text{dp}[i-1][w] \quad \text{if } w_i > w. ]

Implement a solution that reads the input from standard input and writes the output to standard output.

inputFormat

The first line contains two integers \(n\) and \(W\) where \(n\) is the number of souvenirs and \(W\) is the maximum weight the backpack can carry.

The second line contains \(n\) space-separated integers representing the weights \(w_1, w_2, \dots, w_n\) of the souvenirs.

The third line contains \(n\) space-separated integers representing the values \(v_1, v_2, \dots, v_n\) of the souvenirs.

outputFormat

Output a single integer which is the maximum total value of the souvenirs that can be carried without exceeding the weight limit.

## sample

4 5
2 3 4 5
3 4 5 6

7