K Distinct 0/1 Knapsack Solutions with Maximum Total Value

DD and his friends want to go hiking. They have a total of K people and each person carries a backpack of the same capacity V. There are N kinds of items available, each with a specified volume and value. A valid backpack arrangement for a person must satisfy the following conditions:

• The total volume of items in the backpack is exactly V.
• For each backpack, every item can be taken at most once (0/1 knapsack rule), though the same item may appear in different backpacks.
• The list of items in any two backpacks must not be identical.

Under these conditions, determine the maximum possible sum of values of all items placed in the K backpacks. In other words, choose K distinct knapsack solutions (each is a subset of items whose total volume is exactly V) so that the sum of their values is maximized. If it is impossible to choose K distinct valid solutions, output -1.

The optimal substructure is similar to computing the top K best solutions for the classical 0/1 knapsack (with the constraint that the knapsacks must be exactly full), where duplicate value sums coming from different item combinations count as distinct solutions.

Mathematically, if S is the set of all valid knapsack solutions (each solution s has total value \(f(s)\)), we want to choose K distinct solutions \(s_1, s_2, \ldots, s_K \in S\) such that

\[ \max \sum_{i=1}^{K} f(s_i), \]

subject to the constraint that for any two indices \(i \neq j\), the set of items in \(s_i\) is not equal to the set in \(s_j\).

inputFormat

The first line contains three positive integers: N (the number of items), V (the capacity of each backpack) and K (the number of people).

Then follow N lines, each containing two integers: the volume and the value of an item.

You may assume that the input is such that all valid knapsack solutions (i.e. subsets of items with total volume exactly V) have non‐negative values.

outputFormat

Output a single integer representing the maximum total value of items in the K backpacks. If there are fewer than K distinct valid knapsack solutions, output -1.

sample

6 5 2
1 1
2 2
2 4
3 5
3 6
4 7

19