数据很小，n = 20，这个应该可以直接搜索吧，我没试，我用的是折半搜索+二分+线段树维护区间最值，折半搜索就是先搜前10个，然后搜后10个，搜前10个的时候把每一个结果用一个pair<花费，权值>保存下来，然后按照花费排序，在第二次搜索的时候对于当前ww , vv需要的是一个前面搜索满足条件v<=m - vv的ww的最大值，然后就用一个线段树维护就行
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #pragma GCC optimize(3 , "Ofast" , "inline") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization("unroll-loops") #include <iostream> #include <cstdio> #include <algorithm> #include <unordered_map> #include <vector> #include <map> #include <list> #include <queue> #include <cstring> #include <cstdlib> #include <ctime> #include <cmath> #include <stack> #include <set> #include <bitset> #include <deque> using namespace std ; #define ios ios::sync_with_stdio(false) , cin.tie(0) #define x first #define y second #define pb push_back #define ls rt << 1 #define rs rt << 1 | 1 typedef long long ll ; const double esp = 1e-6 , pi = acos(-1) ; typedef pair<ll , ll> PII ; const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7; int ca = 0 ; ll c[30][6] , w[30][6] , a[40] ; ll n , m ; PII b[N] ; int cnt = 0 ; ll maxn[N] ; void up(int rt) { maxn[rt] = max(maxn[ls] , maxn[rs]) ; return ; } void build(int rt , int l , int r) { if(l == r) { maxn[rt] = b[l].y ; return ; } int mid = l + r >> 1 ; build(ls , l , mid) ; build(rs , mid + 1 , r) ; up(rt) ; return ; } ll ask(int rt , int l , int r , int ql , int qr) { if(ql <= l && r <= qr ) { return maxn[rt] ; } ll ans = -1e18 ; int mid = l + r >> 1; if(ql <= mid) ans = max(ans , ask(ls , l , mid , ql , qr)) ; if(qr > mid) ans = max(ans , ask(rs , mid + 1 , r , ql , qr)) ; return ans ; } void dfs(int u , ll ww , ll vv) { if(u == n / 2 + 1) { b[++ cnt] = {vv , ww} ; return ; } for(int i = 0 ;i <= a[u] ;i ++ ) if(vv + c[u][i] <= m) dfs(u +1 , ww + w[u][i] , vv + c[u][i]) ; return ; } ll ans = 0 ; void dfs1(int u , ll ww , ll vv) { if(u == n + 1) { ll t ; int l = 1 , r = cnt ; while(l <= r) { int mid = l + r >> 1 ; if(b[mid].x <= m - vv) l = mid + 1 , t = mid ; else r = mid - 1; } if(t >= 1) { ll res = ask(1 , 1 , cnt , 1 , t) ; ans = max(ans , ww + res) ; } return ; } for(int i = 0 ;i <= a[u] ;i ++ ) if(vv + c[u][i] <= m) dfs1(u +1 , ww + w[u][i] , vv + c[u][i]) ; return ; } int work() { cin >> n >> m ; cnt = 0 ; for(int i = 1; i <= n ;i ++ ) { ll ww , vv , k ; cin >> a[i] ; for(int j = 1; j <= a[i] ;j ++ ) { cin >> ww >> vv ; w[i][j] = w[i][j - 1] + ww ; c[i][j] = c[i][j - 1] + vv ; } } ans = 0 ; dfs(1 , 0 , 0) ; sort(b + 1 , b + cnt + 1) ; build(1 , 1 , cnt) ; dfs1(n / 2 + 1 , 0 , 0) ; printf("Case #%d: %lld\n" , ++ ca , ans) ; return 0 ; } int main() { // freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ; // freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ; int n ; cin >> n ; while(n --) work() ; return 0 ; } /* */