二维费用与分组背包

// 二维费用背包 —— 暴力：2ⁿ 枚举子集
//
// 为什么这一章前半段的标准答案又是「枚举子集」：因为二维费用背包的**题目**
// 和 01 背包一模一样 —— 每件物品还是「拿或不拿」，只是「拿」这个动作现在要
// 同时付出两种代价（重量和体积），而背包对两种代价各有一个上限。
//
// 所以第 23 章那份 2ⁿ 暴力原样就能改：枚举完一个子集，从「只检查重量」
// 变成「重量和体积都要检查」。★ 这正是这半章唯一的新东西 ——
// **多一维费用，只是多一个要同时满足的限制。**
//
// 题意：n 件物品，第 i 件价值 v[i]、重量 w[i]、体积 u[i]，每件最多拿一件。
//       背包重量上限 W、体积上限 V。求最大总价值。
// 输入：第一行 n W V，接下来 n 行每行三个数 v w u
// 输出：最大总价值
//
// ⚠ 只能用在很小的数据上（vol2Gen.cpp 造的是 n ≤ 8）。n = 30 时 2ⁿ 就是十亿。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W, V;
    if (!(cin >> n >> W >> V)) return 0;
    vector<long long> v(n), w(n), u(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> u[i];

    long long best = 0;
    for (long long s = 0; s < (1LL << n); s++) {
        long long sw = 0, su = 0, sv = 0;
        for (int i = 0; i < n; i++)
            if (s >> i & 1) { sw += w[i]; su += u[i]; sv += v[i]; }
        // ★ 和第 23 章唯一的差别就在这一行：两个上限都要满足
        if (sw <= W && su <= V) best = max(best, sv);
    }
    cout << best << "\n";
    return 0;
}

// 二维费用背包 —— 正解：01 背包多加一层循环
//
// 状态从 f[j] 变成 f[j][u]：「重量不超过 j、体积不超过 u 时的最大价值」。
// 转移和第 23 章长得一模一样，只是下标多了一维：
//
//     f[j][u] = max( f[j][u],  f[j - w][u - vol] + v )
//                               ↑↑↑ 右边的第一维（物品维）仍然是 i-1
//
// ★ 所以第 24 章那张「写 i 还是 i-1」的表**原样就能用**：
//   每件最多拿一件 → 右边必须是 i-1 → 一维压缩之后要倒序。
//   多出来的那一维费用**没有改变任何一件事**，它只是多了一层循环。
//
// ⚠ 关于「两层容量循环都要倒序」这句口诀 —— 它多记了一半，真相见 vol2In.cpp：
//   决定「读到的是上一轮还是这一轮」的只有**外层**那一维。
//   这里两层都写倒序，是因为这样最好记、也最不容易出错。
//
// 时间 O(nWV)，空间 O(WV)。
// 输入输出同 vol2Brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W, V;
    if (!(cin >> n >> W >> V)) return 0;

    // f[j][u]：重量不超过 j、体积不超过 u 时的最大价值
    vector<vector<long long>> f(W + 1, vector<long long>(V + 1, 0));

    for (int i = 0; i < n; i++) {
        long long v, w, vol;
        cin >> v >> w >> vol;
        for (long long j = W; j >= w; j--)                 // ★ 外层倒序：读到的必须是「还没放这件物品」的值
            for (long long u = V; u >= vol; u--)           //   内层跟着倒序（好记；其实方向无所谓，见 vol2In.cpp）
                f[j][u] = max(f[j][u], f[j - w][u - vol] + v);
    }

    cout << f[W][V] << "\n";
    return 0;
}

// 二维费用背包：外层倒序、**内层正序** —— 这一份不是 bug，它是对的
//
// 为什么要专门留一份「看起来写错了」的代码：因为「两层容量循环都要倒序」这句口诀，
// 有一半是白记的。这份代码就是证据 —— 它在 300 组数据上和 vol2.cpp **一模一样**，
// 一组都不差（check:viz 钉着这一条）。
//
// ★ 真正的规则从来只有一句：**读 f[j-w][u-vol] 时，读到的必须是「还没放这件物品」的值。**
//
//   而 f 是按外层下标 j 分成一整行一整行的。外层倒序时，j-w < j 那一整行
//   **这一轮根本还没被碰过** —— 里面每一格都还是上一轮的值。
//   既然整行都没动过，那内层在这一行里从左往右还是从右往左读，读到的是同一个东西。
//
//   反过来，外层一旦正序，j-w 那一整行**已经全部更新完了**，
//   内层再怎么倒序也救不回来（那就是 vol2Up.cpp，它解的是完全背包）。
//
// ⚠ 前提是 w ≥ 1。如果允许出现重量为 0 的物品，j-w 就是 j 自己（同一行），
//   上面这套「整行还没动过」的论证立刻失效，内层的方向就又要命了。
//   —— 又一个「题目对边界的约定必须抄进注释」的例子。
//
// 结论不是「以后内层随便写」，而是：知道为什么之后，**你只需要盯住外层**。
// 平时仍然建议两层都写倒序，因为那样不用每次都想一遍。
//
// 输入输出同 vol2Brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W, V;
    if (!(cin >> n >> W >> V)) return 0;

    vector<vector<long long>> f(W + 1, vector<long long>(V + 1, 0));

    for (int i = 0; i < n; i++) {
        long long v, w, vol;
        cin >> v >> w >> vol;
        for (long long j = W; j >= w; j--)                 // 外层倒序 —— 说了算的是它
            for (long long u = vol; u <= V; u++)           // 内层正序 —— 一点关系都没有
                f[j][u] = max(f[j][u], f[j - w][u - vol] + v);
    }

    cout << f[W][V] << "\n";
    return 0;
}

// ✗ 故意写错（一）：二维费用背包，**外层容量循环写成了正序**
//
// 和 vol2.cpp 只差一个方向：
//     正确： for (j = W; j >= w; j--)      本文件： for (j = w; j <= W; j++)
//
// 它不会崩、不会报错，只是安静地给你另一道题的正确答案 ——
// **它解的是二维费用的完全背包**（每件可以拿无限件），也就是 vol2Full.cpp。
//
// 为什么：j 正序时，读 f[j-w][...] 会读到「本轮已经放过这件物品」的那一行，
// 于是同一件物品可以一而再、再而三地被放进去。
// 这就是第 23 章「正序解的是完全背包」在二维里的原样重演。
//
// check:viz 用 300 组数据钉死了这条恒等式：本文件的输出 ≡ vol2Full.cpp 的输出。
//
// 内层的方向在这里是**故意保留倒序**的 —— 为的是说清楚一件事：
// 内层写什么方向都救不回来，**方向的决定权只在外层**（对照 vol2In.cpp）。
//
// 输入输出同 vol2Brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W, V;
    if (!(cin >> n >> W >> V)) return 0;

    vector<vector<long long>> f(W + 1, vector<long long>(V + 1, 0));

    for (int i = 0; i < n; i++) {
        long long v, w, vol;
        cin >> v >> w >> vol;
        for (long long j = w; j <= W; j++)                 // ✗ 正序 —— 这一件事就把题目换掉了
            for (long long u = V; u >= vol; u--)           // 内层仍然是倒序，但救不回来
                f[j][u] = max(f[j][u], f[j - w][u - vol] + v);
    }

    cout << f[W][V] << "\n";
    return 0;
}

// 把二维费用的**四种循环方向**并排跑成一张表
//
// 为什么要有这份代码：正文里那句「只有外层方向说了算」是推出来的，
// 推理再顺也不如把四种写法摆在同一组数据上，让答案自己说话。
//
// 四行输出对应四种写法（外层容量循环 × 内层容量循环，各有正序 / 倒序）：
//
//     倒序 + 倒序   ← vol2.cpp，正解（01 背包）
//     倒序 + 正序   ← vol2In.cpp，**也是正解**（内层方向根本不影响）
//     正序 + 倒序   ← vol2Up.cpp，解的是完全背包
//     正序 + 正序   ←            同样是完全背包
//
// 最后两列是「和第一行一样吗」「和第三行一样吗」，也就是
// **这种写法解的到底是 01 背包还是完全背包**。
// 你会看到答案按外层方向分成整整齐齐的两组，内层那一列从头到尾没起过作用。
//
// 输入输出：输入同 vol2Brute.cpp；不给输入就用一组内置的默认数据（正文和动画用的那一组）。
//
// ⚠ 表头里一个数字都不能有 —— check-viz 是按行里的数字解析这张表的
//   （第 20 章的 knapTable.cpp 踩过这个坑）。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w, u; };

// outerUp / innerUp：那一层是不是正序
static long long solve(const vector<Item>& it, long long W, long long V,
                       bool outerUp, bool innerUp) {
    vector<vector<long long>> f(W + 1, vector<long long>(V + 1, 0));
    for (const auto& x : it) {
        if (outerUp) {
            for (long long j = x.w; j <= W; j++) {
                if (innerUp) for (long long u = x.u; u <= V; u++) f[j][u] = max(f[j][u], f[j - x.w][u - x.u] + x.v);
                else         for (long long u = V; u >= x.u; u--) f[j][u] = max(f[j][u], f[j - x.w][u - x.u] + x.v);
            }
        } else {
            for (long long j = W; j >= x.w; j--) {
                if (innerUp) for (long long u = x.u; u <= V; u++) f[j][u] = max(f[j][u], f[j - x.w][u - x.u] + x.v);
                else         for (long long u = V; u >= x.u; u--) f[j][u] = max(f[j][u], f[j - x.w][u - x.u] + x.v);
            }
        }
    }
    return f[W][V];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W, V;
    vector<Item> it;
    if (cin >> n >> W >> V) {
        it.resize(n);
        for (auto& x : it) cin >> x.v >> x.w >> x.u;
    } else {
        // 默认数据：正文第二步手算的那一组（重量和体积**各自都会吃紧**）
        W = 10; V = 8;
        it = {{6, 4, 2}, {5, 3, 4}, {4, 2, 3}, {3, 2, 2}};
    }

    const long long down = solve(it, W, V, false, false);   // 两层都倒序 = 01 背包
    const long long up   = solve(it, W, V, true,  false);   // 外层正序   = 完全背包

    // ⚠ 这里的空格是**手数出来的**，没有用 setw 对齐中文 ——
    //   setw 数的是字节数，而一个汉字占 3 个字节、却只占 2 格宽，对出来必歪。
    //   （每个中文字段的内容宽度都是固定的，所以直接补固定个数的空格最省事。）
    cout << "  外层容量循环   内层容量循环     答案   和两层都倒序一样   和两层都正序一样\n";
    cout << "  ------------   ------------   ------   ----------------   ----------------\n";
    for (int o = 0; o < 2; o++)
        for (int i = 0; i < 2; i++) {
            long long ans = solve(it, W, V, o == 1, i == 1);
            cout << "  " << (o == 1 ? "正序" : "倒序") << "           "     // 4 格宽 + 11 空格
                 << (i == 1 ? "正序" : "倒序") << "           "
                 << setw(6) << ans << "   "
                 << (ans == down ? "是" : "否") << "                 "      // 2 格宽 + 17 空格
                 << (ans == up ? "是" : "否") << "\n";
        }
    return 0;
}

// 二维费用背包 —— 正解：01 背包多加一层循环
//
// 状态从 f[j] 变成 f[j][u]：「重量不超过 j、体积不超过 u 时的最大价值」。
// 转移和第 23 章长得一模一样，只是下标多了一维：
//
//     f[j][u] = max( f[j][u],  f[j - w][u - vol] + v )
//                               ↑↑↑ 右边的第一维（物品维）仍然是 i-1
//
// ★ 所以第 24 章那张「写 i 还是 i-1」的表**原样就能用**：
//   每件最多拿一件 → 右边必须是 i-1 → 一维压缩之后要倒序。
//   多出来的那一维费用**没有改变任何一件事**，它只是多了一层循环。
//
// ⚠ 关于「两层容量循环都要倒序」这句口诀 —— 它多记了一半，真相见 vol2In.cpp：
//   决定「读到的是上一轮还是这一轮」的只有**外层**那一维。
//   这里两层都写倒序，是因为这样最好记、也最不容易出错。
//
// 时间 O(nWV)，空间 O(WV)。
// 输入输出同 vol2Brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W, V;
    if (!(cin >> n >> W >> V)) return 0;

    // f[j][u]：重量不超过 j、体积不超过 u 时的最大价值
    vector<vector<long long>> f(W + 1, vector<long long>(V + 1, 0));

    for (int i = 0; i < n; i++) {
        long long v, w, vol;
        cin >> v >> w >> vol;
        for (long long j = W; j >= w; j--)                 // ★ 外层倒序：读到的必须是「还没放这件物品」的值
            for (long long u = V; u >= vol; u--)           //   内层跟着倒序（好记；其实方向无所谓，见 vol2In.cpp）
                f[j][u] = max(f[j][u], f[j - w][u - vol] + v);
    }

    cout << f[W][V] << "\n";
    return 0;
}

// 分组背包 —— 暴力：DFS 枚举「每一组选哪一件（或者一件都不选）」
//
// ★ 它是**完全不同的思路**：不做 DP、不压维、根本不关心循环顺序，
//   只是把「每组的选择」全排一遍。这一点很重要 ——
//   这一章的三个错误版本全都是「顺序写错」，而顺序写错的代码之间是会互相「印证」的
//   （第 20 章那条规矩：**标准答案最好用完全不同的思路写出来**）。
//
// 复杂度 ∏(每组件数 + 1)：5 组每组 3 件就是 4⁵ = 1024，还行；
// 15 组每组 3 件就是 4¹⁵ ≈ 十亿，跑不动了 —— 正文第 12 步会实测这条曲线。
//
// 题意：物品被分成 g 组，**每组至多选一件**（也可以不选）。背包容量 W，求最大总价值。
// 输入：第一行 g W
//       接下来 g 行，每行先是这一组的件数 cnt，再跟 cnt 对「价值 重量」
// 输出：最大总价值
//
// 这个「每行一组」的输入格式是本章自己定的，好处是分组关系一眼可见；
// 洛谷 P1757 是「每件物品自带组号」，读入时归一下类就变成这个样子。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w; };

int g;
long long W, best;
vector<vector<Item>> grp;

// 处理到第 gi 组，还剩 rest 容量，已经攒了 got 的价值
void dfs(int gi, long long rest, long long got) {
    if (gi == g) { best = max(best, got); return; }
    dfs(gi + 1, rest, got);                             // 这一组一件都不选
    for (const auto& it : grp[gi])                      // 或者恰好选一件
        if (it.w <= rest) dfs(gi + 1, rest - it.w, got + it.v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> g >> W)) return 0;
    grp.resize(g);
    for (int i = 0; i < g; i++) {
        int cnt;
        cin >> cnt;
        grp[i].resize(cnt);
        for (auto& it : grp[i]) cin >> it.v >> it.w;
    }

    best = 0;
    dfs(0, W, 0);
    cout << best << "\n";
    return 0;
}

// 分组背包 —— 正解。★ 这一章真正的新东西，而它全部的难点就是**三层循环的顺序**
//
//     for (每一组 gi)                       ← 组在最外层
//         for (j = W; j >= 0; j--)          ← 容量在中间，倒序
//             for (这一组里的每一件 it)      ← 组内枚举在最里层
//                 f[j] = max(f[j], f[j - it.w] + it.v);
//
// ★ 为什么必须是这个顺序 —— 还是那一句话，和第 23、24 章一字不差：
//   **看你读到的 f[j - w] 是「上一轮」的还是「这一轮」的。**
//
//   这里的「一轮」不再是一件物品，而是**一整组**。
//   j 倒序时，f[j - w] 还没被这一组碰过 —— 它代表「前 gi-1 组的最优解」，
//   在它上面加一件，这一组就正好只出了一件。「每组至多一件」是这么保证的。
//
//   如果把组内那层循环提到容量循环外面（groupFlat.cpp），
//   同一组的第二件物品就会读到「第一件已经放进去」的 f，于是一组能选两件 ——
//   那就退化成了无视分组的普通 01 背包。
//   如果把容量写成正序（groupUp.cpp），同一件还能被反复拿 —— 那是完全背包。
//
// ⚠ 注意 j 要一直倒序到 0（而不是到某个 w[i] 为止）—— 因为内层每件物品的重量不同，
//   下界只能在最里面用 `it.w <= j` 判，不能提到中层循环的边界上。
//
// 时间 O(W × 总件数)，空间 O(W)。
// 输入输出同 groupBrute.cpp。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int g;
    long long W;
    if (!(cin >> g >> W)) return 0;
    vector<vector<Item>> grp(g);
    for (int i = 0; i < g; i++) {
        int cnt;
        cin >> cnt;
        grp[i].resize(cnt);
        for (auto& it : grp[i]) cin >> it.v >> it.w;
    }

    vector<long long> f(W + 1, 0);

    for (int gi = 0; gi < g; gi++)                       // ① 组
        for (long long j = W; j >= 0; j--)               // ② 容量，倒序
            for (const auto& it : grp[gi])               // ③ 组内枚举 —— 必须在最里层
                if (it.w <= j) f[j] = max(f[j], f[j - it.w] + it.v);

    cout << f[W] << "\n";
    return 0;
}

// ✗ 故意写错（三）：把**组内枚举那层循环提到了容量循环外面**
//
// 和 group.cpp 只差两行的先后顺序：
//
//     正确： for (组) for (j = W..0)  for (组内每件)
//     本文件：for (组) for (组内每件) for (j = W..0)      ← 中间两层换了个位置
//
// 这是分组背包唯一的、也是最容易犯的错误，而且它**不会报错、不会崩溃**。
//
// ★ 它解的是另一道题：**无视分组的普通 01 背包**（groupIgnore.cpp）。
//   因为这样一来，同一组的第二件物品读 f[j-w] 时，读到的是「第一件已经放进去」的值 ——
//   于是一组里能选出两件、三件。分组这个限制被整个抹掉了。
//
//   而「组内枚举」这层循环放在最里面时，它读的 f[j-w] 还没被本组任何一件动过，
//   所以本组最多只能出一件。**同样三层循环，换个顺序就是另一道题。**
//
// check:viz 用 300 组数据钉死了这条恒等式：本文件的输出 ≡ groupIgnore.cpp 的输出。
// 这是第 23 章（正序 ≡ 完全背包）、第 24 章（倒序 ≡ 01 背包）之后，
// 同一个现象的第三次出现。
//
// 输入输出同 groupBrute.cpp。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int g;
    long long W;
    if (!(cin >> g >> W)) return 0;
    vector<vector<Item>> grp(g);
    for (int i = 0; i < g; i++) {
        int cnt;
        cin >> cnt;
        grp[i].resize(cnt);
        for (auto& it : grp[i]) cin >> it.v >> it.w;
    }

    vector<long long> f(W + 1, 0);

    for (int gi = 0; gi < g; gi++)
        for (const auto& it : grp[gi])                   // ✗ 组内枚举跑到了外面
            for (long long j = W; j >= it.w; j--)
                f[j] = max(f[j], f[j - it.w] + it.v);

    cout << f[W] << "\n";
    return 0;
}

// ✗ 故意写错（四）：分组背包的**容量循环写成了正序**
//
// 三层循环的位置全对，只有中间那层的方向反了：
//
//     正确： for (组) for (j = W; j >= 0; j--)  for (组内每件)
//     本文件：for (组) for (j = 0; j <= W; j++)  for (组内每件)
//
// ★ 它解的又是另一道题：**无视分组的完全背包**（groupFull.cpp）——
//   正序意味着 f[j-w] 已经被本组更新过，于是本组的物品可以被反复拿，
//   想拿几件拿几件，还能混着拿。「每组至多一件」被彻底放开了。
//
// 于是分组背包这一章有了一张很漂亮的表：**两种写错顺序的方式，
// 正好分别是第 23 章和第 24 章的正确答案。**
//
//     组内枚举提到容量外  → 01 背包（每件至多一件，但不管分组）
//     容量循环写成正序    → 完全背包（每件想拿几件拿几件）
//     两个都写对          → 分组背包（每组至多一件）
//
// 三道题，同样三层循环，区别只在顺序。这也是为什么这一章反复强调：
// **别背口诀，问自己「我读到的 f[j-w] 是这一轮的还是上一轮的」。**
//
// check:viz 用 300 组数据钉死了这条恒等式：本文件的输出 ≡ groupFull.cpp 的输出。
//
// 输入输出同 groupBrute.cpp。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int g;
    long long W;
    if (!(cin >> g >> W)) return 0;
    vector<vector<Item>> grp(g);
    for (int i = 0; i < g; i++) {
        int cnt;
        cin >> cnt;
        grp[i].resize(cnt);
        for (auto& it : grp[i]) cin >> it.v >> it.w;
    }

    vector<long long> f(W + 1, 0);

    for (int gi = 0; gi < g; gi++)
        for (long long j = 0; j <= W; j++)               // ✗ 正序
            for (const auto& it : grp[gi])
                if (it.w <= j) f[j] = max(f[j], f[j - it.w] + it.v);

    cout << f[W] << "\n";
    return 0;
}

// ✗ 故意写错（五）：把「每组**至多**选一件」写成了「每组**必须**选一件」
//
// 前两个错误都是顺序问题，这一个是**读题问题** —— 而且它藏在一个很不起眼的地方：
//
//     正确： f[j] = max(f[j], f[j - w] + v);      ← f[j] 自己也在候选里 = 可以不选
//     本文件：best = 组内所有件里最大的那个；f[j] = best;   ← 把 f[j] 挤掉了
//
// 少写的那个「f[j] 自己」，就是「这一组一件都不选」这个选项。
// 它一没了，每一组就都被逼着出一件，答案只会变小（有时小很多）。
//
// ⚠ 这类 bug 的特点是**在小数据上经常蒙对** —— 只要每组都「选一件比不选强」，
//   两份代码的答案就一样。所以生成器必须造出「这一组里的东西又重又不值钱」的局面
//   （groupGen.cpp 的 kind 2 就是干这个的）。
//
// 顺带一提：真有题目要求「每组必须选一件」，那就是**另一道题**，
// 正确写法是把 f 的初值设成 -∞ 再单独处理（第 23 章 exact.cpp 那个「恰好装满」的套路）。
// 而不是像这里一样，糊里糊涂地把「不选」这个选项弄丢。
//
// 输入输出同 groupBrute.cpp。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int g;
    long long W;
    if (!(cin >> g >> W)) return 0;
    vector<vector<Item>> grp(g);
    for (int i = 0; i < g; i++) {
        int cnt;
        cin >> cnt;
        grp[i].resize(cnt);
        for (auto& it : grp[i]) cin >> it.v >> it.w;
    }

    vector<long long> f(W + 1, 0);

    for (int gi = 0; gi < g; gi++)
        for (long long j = W; j >= 0; j--) {
            long long best = -1;
            for (const auto& it : grp[gi])
                if (it.w <= j) best = max(best, f[j - it.w] + it.v);   // ✗ 没有把 f[j] 放进候选
            if (best >= 0) f[j] = best;                                // ✗ 直接覆盖 = 这一组必须出一件
        }

    cout << f[W] << "\n";
    return 0;
}

// 分组背包 —— 正解。★ 这一章真正的新东西，而它全部的难点就是**三层循环的顺序**
//
//     for (每一组 gi)                       ← 组在最外层
//         for (j = W; j >= 0; j--)          ← 容量在中间，倒序
//             for (这一组里的每一件 it)      ← 组内枚举在最里层
//                 f[j] = max(f[j], f[j - it.w] + it.v);
//
// ★ 为什么必须是这个顺序 —— 还是那一句话，和第 23、24 章一字不差：
//   **看你读到的 f[j - w] 是「上一轮」的还是「这一轮」的。**
//
//   这里的「一轮」不再是一件物品，而是**一整组**。
//   j 倒序时，f[j - w] 还没被这一组碰过 —— 它代表「前 gi-1 组的最优解」，
//   在它上面加一件，这一组就正好只出了一件。「每组至多一件」是这么保证的。
//
//   如果把组内那层循环提到容量循环外面（groupFlat.cpp），
//   同一组的第二件物品就会读到「第一件已经放进去」的 f，于是一组能选两件 ——
//   那就退化成了无视分组的普通 01 背包。
//   如果把容量写成正序（groupUp.cpp），同一件还能被反复拿 —— 那是完全背包。
//
// ⚠ 注意 j 要一直倒序到 0（而不是到某个 w[i] 为止）—— 因为内层每件物品的重量不同，
//   下界只能在最里面用 `it.w <= j` 判，不能提到中层循环的边界上。
//
// 时间 O(W × 总件数)，空间 O(W)。
// 输入输出同 groupBrute.cpp。

#include <bits/stdc++.h>
using namespace std;

struct Item { long long v, w; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int g;
    long long W;
    if (!(cin >> g >> W)) return 0;
    vector<vector<Item>> grp(g);
    for (int i = 0; i < g; i++) {
        int cnt;
        cin >> cnt;
        grp[i].resize(cnt);
        for (auto& it : grp[i]) cin >> it.v >> it.w;
    }

    vector<long long> f(W + 1, 0);

    for (int gi = 0; gi < g; gi++)                       // ① 组
        for (long long j = W; j >= 0; j--)               // ② 容量，倒序
            for (const auto& it : grp[gi])               // ③ 组内枚举 —— 必须在最里层
                if (it.w <= j) f[j] = max(f[j], f[j - it.w] + it.v);

    cout << f[W] << "\n";
    return 0;
}