#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5; #define INF 1e8 int n; int t; int dp[maxn][maxn]; int cost[maxn]; int val[maxn]; int main() { while(scanf("%d%d",&n,&t)==2) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { int m,s; scanf("%d%d",&m,&s); for(int k=1;k<=m;k++) scanf("%d%d",&cost[k],&val[k]); if(s==0)//最少選1個的01背包問題 { for(int j=0;j<=t;j++) dp[i][j]=-INF; for(int k=1;k<=m;k++) for(int j=t;j>=cost[k];j--) { dp[i][j] = max( dp[i][j] , dp[i][j-cost[k]]+val[k] ); //1 dp[i][j] = max( dp[i][j] , dp[i⑴][j-cost[k]]+val[k] );//2 //上面兩句順序互換就會出錯!為何? } } else if(s==1)//最多選1個的背包問題 { for(int j=0;j<=t;j++) dp[i][j]=dp[i⑴][j]; for(int k=1;k<=m;k++) for(int j=t;j>=cost[k];j--)//j可以正序或逆序枚舉 dp[i][j] = max( dp[i][j] , dp[i⑴][j-cost[k]]+val[k] ); } else if(s==2)//隨意選的01背包問題 { for(int j=0;j<=t;j++) dp[i][j]=dp[i⑴][j]; for(int k=1;k<=m;k++) for(int j=t;j>=cost[k];j--)//j只能逆序枚舉 dp[i][j] = max( dp[i][j] , dp[i][j-cost[k]]+val[k] ); } } int ans = max(dp[n][t],⑴); printf("%d ",ans); } return 0; }