Knapsack Optimization Problem

You are given a knapsack with a maximum capacity \(W\) and \(N\) items. Each item has a weight and a value. Your task is to determine the maximum total value you can achieve by selecting a subset of these items such that their total weight does not exceed \(W\). This is a classic 0/1 knapsack problem.

The recurrence used is:

\(dp[i][w] = \max\left(dp[i-1][w], dp[i-1][w-w_i] + v_i\right)\), if \(w_i \le w\), otherwise \(dp[i][w] = dp[i-1][w]\).

Implement the solution using dynamic programming.

inputFormat

The first line contains two integers \(W\) and \(N\) separated by a newline. \(W\) denotes the maximum weight capacity of the knapsack, and \(N\) denotes the number of items.

The second line contains \(N\) space-separated integers representing the weights of the items.

The third line contains \(N\) space-separated integers representing the values of the items.

outputFormat

Output a single integer which is the maximum value that can be achieved without exceeding the capacity \(W\).

10
4
5 4 6 3
10 40 30 50

90