1 /* 2 有n组背包，每组都有限制 3 0、至少选一项 4 1、最多选一项 5 2、任意选 6 */ 7 #include <iostream> 8 #include <cstdio> 9 #include <cstring>10 using namespace std;11 12 const int maxn=105;13 const int INF=0xfffffff;14 int dp[maxn][maxn];//第i组,剩余时间j的最大价值15 int w[maxn],v[maxn];16 inline int max(int a,int b){return a>b?a:b;}17 int main()18 {19     int n,t,m,flag,i,j,k;20     while(~scanf("%d%d",&n,&t))21     {22         memset(dp[0],0,sizeof(dp));23         for(i=1;i<=n;i++)24         {25             scanf("%d%d",&m,&flag);26             for(j=1;j<=m;j++) scanf("%d%d",w+j,v+j);27             if(flag==0)28             {29                 for(j=0;j<=t;j++) dp[i][j]=-INF;30                 for(j=1;j<=m;j++)31                     for(k=t;k-w[j]>=0;k--)32                         dp[i][k]=max(dp[i][k],max(dp[i-1][k-w[j]]+v[j],dp[i][k-w[j]]+v[j]));//这组不选,第一次选,多次选33             }34             else if(flag==1)35             {36                 for(j=0;j<=t;j++) dp[i][j]=dp[i-1][j];37                 for(j=1;j<=m;j++)38                     for(k=t;k-w[j]>=0;k--)39                         dp[i][k]=max(dp[i][k],dp[i-1][k-w[j]]+v[j]);//这组不选,第一次选40             }41             else42             {43                 for(j=0;j<=t;j++) dp[i][j]=dp[i-1][j];44                 for(j=1;j<=m;j++)45                     for(k=t;k-w[j]>=0;k--)46                         dp[i][k]=max(dp[i][k],max(dp[i-1][k-w[j]]+v[j],dp[i][k-w[j]]+v[j]));//这组不选,第一次选，多次选47             }48         }49         int ans=max(dp[n][t],-1);50         printf("%d\n",ans);51     }52     return 0;53 }