Multiple-Choice Knapsack

Inspired by the classic 0-1 knapsack problem, this problem introduces a twist: instead of a single set of items, the items are divided into k groups. In each group, the items conflict with each other, meaning that at most one item can be selected per group. Additionally, you are given a knapsack of limited capacity W. Your task is to choose at most one item from each group such that the total weight does not exceed W and the total value is maximized.

Problem Formulation:

You are given an integer k representing the number of groups and an integer W representing the maximum capacity of the knapsack. For each group, you are given an integer m (the number of items in the group) followed by m pairs of integers; each pair represents the weight and value of an item. You may select at most one item from each group (or skip the group entirely). Determine the maximum total value achievable without exceeding the knapsack capacity W.

Mathematical Model (in LaTeX):

Let there be k groups with items in group i given by \(\{(w_{ij}, v_{ij})\}_{j=1}^{m_i}\). We wish to choose an item \(x_i\) from each group such that \(x_i \in \{0,1,\dots, m_i\}\), where \(x_i=0\) means no item is chosen, and for \(x_i \ge 1\) the item chosen is \((w_{i,x_i}, v_{i,x_i})\). The constraint and objective can be formulated as:

[ \begin{aligned} \text{maximize} \quad & \sum_{i=1}^k \delta(x_i),v_{i,x_i} \ \text{subject to} \quad & \sum_{i=1}^k \delta(x_i),w_{i,x_i} \leq W, \ \end{aligned} ]

where \(\delta(x_i) = 0\) if \(x_i = 0\) and \(\delta(x_i) = 1\) if \(x_i \ge 1\).

inputFormat

The first line contains two integers k and W (1 ≤ k ≤ 100, 1 ≤ W ≤ 10⁴), representing the number of groups and the knapsack capacity respectively.

Then for each of the k groups, the input is given as follows:

• The first line of the group contains an integer m (1 ≤ m ≤ 100), the number of items in the group.
• Each of the next m lines contains two integers, representing the weight and the value of an item.

outputFormat

Output a single integer, the maximum total value that can be achieved under the given constraints.

sample

2 10
2
3 4
4 5
3
4 5
5 8
3 4

13