nowcoder xinjun与阴阳师

阴阳师"/>

nowcoder xinjun与阴阳师

/*
看似是完全背包的题目
可以看成是稍微加了种类限制的01背包
所以三重循环解决
第一重是种类
第二重是容量
第三重是每一种中选择一个模式不断更新dp一维数组
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;int n, m, dp[N];
vector <int> a[N], b[N];//a存贮价值，b存储花费int main()
{int T;scanf("%d", &T);while (T--){scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i)a[i].clear(), b[i].clear();for (int i = 1; i <= n; ++i){int x;scanf("%d", &x);for (int j = 1; j <= x; ++j){int v;scanf("%d", &v);a[i].push_back(v);}for (int j = 1; j <= x; ++j){int w;scanf("%d", &w);b[i].push_back(w);}}memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; ++i)for (int j = m; j >=0; j--)for (int k = 0; k < a[i].size(); ++k)if (j >= b[i][k])dp[j] = max(dp[j], dp[j - b[i][k]] + a[i][k]);printf("%d\n", dp[m]);}return 0;
}