#include <iostream>
#include <vector>

using namespace std;

// 物品结构体，包含重量和价值
struct Item {
    int weight;
    int value;
    Item(int w, int v) : weight(w), value(v) {}
};

int main() {
    int N, V;  // N 表示物品组的数量，V 表示背包的容量
    cin >> N >> V;

    // 存储分组物品，每个分组是一个 Item 向量
    vector<vector<Item>> groups(N);  

    // 输入每个分组中的物品信息
    for (int i = 0; i < N; ++i) {
        int num;  // 该组内物品的数量
        cin >> num;
        for (int j = 0; j < num; ++j) {
            int w, v;  // 物品的重量和价值
            cin >> w >> v;
            groups[i].push_back(Item(w, v));
        }
    }

    // 二维数组用于动态规划，dp[i][j] 表示前 i 个物品组，背包容量为 j 时的最大价值
     int dp[1010][1010];
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];  // 不选当前组的物品，直接继承上一组的结果
            // 遍历当前组内的物品
            for (const Item& item : groups[i - 1]) { 
                if (j >= item.weight) dp[i][j] = max(dp[i][j], dp[i - 1][j - item.weight] + item.value); 
            }
        }
    }
    cout << dp[N][V] << endl;  
    return 0;
}

转移方程的形式

通常，我们采用动态规划来解决分组背包问题，其核心的状态转移方程大致形式如下（假设\(dp[i][j]\)表示前\(i\)个物品组，背包容量为\(j\)时能获得的最大价值）：

\(cpp dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k.weight] + k.value); \)

这里的\(k\)是遍历第\(i\)个物品组中的各个物品，\(k.weight\)表示物品的重量，\(k.value\)表示物品的价值。内层循环遍历第\(i\)组内的物品，去尝试更新\(dp[i][j]\)的值。

保证同组内只选一个的原理

• 顺序依赖性：在进行动态规划的递推过程中，我们是按照物品组的顺序依次处理的，对于每一组物品，我们去考虑将组内的某个物品放入背包时，此时的状态依赖于没有选择该组内任何物品的状态（也就是 \(dp[i - 1][j]\) 这个状态）以及选择了该组内某个物品后剩余容量情况下的状态（\(dp[i - 1][j - k.weight] + k.value\)）。由于我们是在遍历组内物品时，每次都是基于前\(i - 1\)组已经确定好的最优状态（即已经完成了前面组的选择情况计算）以及当前组内还未选择该物品时的状态来考虑是否选择当前物品，一旦选择了组内的某个物品进入背包，就相当于确定了这一组在当前背包容量下的选择，后续再去更新其他容量对应的状态时，不会再重复选择这组内已经选择过的物品或者再选择这组内的其他物品了。因为每次更新\(dp[i][j]\)都是基于前面组固定的情况以及当前组当前物品选择与否的情况来综合确定的，不会出现同一组内重复选择不同物品来更新同一个状态的情况。
• 更新机制：转移方程的更新逻辑是在每一组物品的遍历中，针对当前背包容量\(j\)，去尝试放入组内不同物品，看是否能得到更优的价值。它是一个“替换”或者“保持”已有最优值的过程，当我们通过选择组内某个物品更新了\(dp[i][j]\)的值后，这个值就代表了在考虑到第\(i\)组物品时，背包容量为\(j\)的当前最优情况，后续再去遍历组内其他物品时，只是去看能否通过选择其他物品来进一步优化这个状态，而不是去累加同组内多个物品的情况，所以自然就保证了同组内只会选择一个物品进入最终的背包方案来构成最优解。