Maximum Nutrient Value

You are given a maximum weight capacity \(W\) and \(n\) items (fruits) where each fruit has an associated weight and nutrient value. Your task is to determine the maximum total nutrient value that can be obtained without exceeding the weight capacity.

This is a classic 0/1 knapsack problem. For each fruit, you can either take it or leave it. The optimal solution is the one that maximizes the nutrient value while keeping the total weight \(\le W\).

The problem can be mathematically formulated as follows:

[ \text{Maximize } \sum_{i=1}^{n} v_i x_i \quad \text{subject to} \quad \sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in {0,1} ]

where \(w_i\) and \(v_i\) are the weight and nutrient value of the \(i\)-th fruit respectively, and \(x_i\) is a binary variable indicating whether the fruit is taken.

inputFormat

The input is given via standard input (stdin) and has three lines:

• The first line contains two integers \(W\) and \(n\), where \(W\) is the maximum weight capacity and \(n\) is the number of fruits.
• The second line contains \(n\) integers representing the weights of the fruits.
• The third line contains \(n\) integers representing the nutrient values of the fruits.

outputFormat

Output a single integer to standard output (stdout) representing the maximum nutrient value that can be achieved without exceeding the weight capacity.

50 3
10 20 30
60 100 120

220