Knapsack Maximum Cost

You are given a knapsack with a maximum weight capacity \(W\) and \(n\) items. Each item has an associated weight and cost. Your task is to determine the maximum cost achievable by selecting a subset of items such that their total weight does not exceed \(W\). This is a classical 0/1 Knapsack problem.

Input Format: The input is provided via standard input with two lines. The first line contains two space-separated integers \(n\) and \(W\). The second line contains \(2n\) space-separated integers: the first \(n\) integers represent the weights of the items and the next \(n\) integers represent the corresponding costs.

Output Format: Print the maximum cost achievable without exceeding the weight capacity \(W\).

The solution requires the use of a dynamic programming approach where the state \(dp[w]\) represents the maximum cost that can be achieved with a weight capacity \(w\). The transition is given by:

[ dp[w] = \max(dp[w], dp[w - \text{weight}_i] + \text{cost}_i) \quad \text{for } w \geq \text{weight}_i ]

Be sure that your solution reads from standard input and writes to standard output.

inputFormat

The input comes in two lines:

• First line: Two space-separated integers \(n\) (number of items) and \(W\) (maximum weight capacity).
• Second line: \(2n\) space-separated integers, where the first \(n\) values are the weights of the items and the following \(n\) values are the corresponding costs.

Input is read from stdin.

outputFormat

Output a single integer representing the maximum cost achievable without exceeding the knapsack's weight capacity \(W\). The output is written to stdout.

## sample

3 50
10 20 30 60 100 120

220