Problem Statement

Group Knapsack with Non-Adjacent Groups You are given N consecutive groups of items and a knapsack with capacity W . Each group lists exactly S item slots. A slot containing -1 -1 is empty and cannot be selected; every other slot contains a positive weight and a non-negative value. Choose items to maximize their total value subject to all of these rules: Select at most one item from each group. If an item is selected from group i , no item may be selected from group i-1 or i+1 . The total selected weight must not exceed W . Input The first line contains N W S . Each of the next N lines contains 2*S integers: w1 v1 w2 v2 ... wS vS . Output Print the maximum total value. Constraints 1 <= N <= 200 1 <= W <= 2000 1 <= S <= 20 A real item has 1 <= weight <= W and 0 <= value <= 10^9 . An empty slot is exactly -1 -1 . The answer may require a 64-bit integer. Example Input: 3 5 2 2 6 4 9 3 8 -1 -1 2 7 5 10 Output: 13 Explanation Choose the weight-2 item of value 6