Alice and Bob are playing "Gems Fight!": 
　　There are Gems of G different colors , packed in B bags. Each bag has several Gems. G different colors are numbered from color 1 to color G. 
　　Alice and Bob take turns to pick one bag and collect all the Gems inside. A bag cannot be picked twice. The Gems collected are stored in a shared cooker. 
　　After a player ,we name it as X, put Gems into the cooker, if there are S Gems which are the same color in the cooker, they will be melted into one Magic Stone. This reaction will go on and more than one Magic Stone may be produced, until no S Gems of the same color remained in that cooker. Then X owns those new Magic Stones. When X gets one or more new Magic Stones, he/she will also get a bonus turn. If X gets Magic Stone in a bonus turn, he will get another bonus turn. In short,a player may get multiple bonus turns continuously. 
　　There will be B turns in total. The goal of "Gems Fight!" is to get as more Magic Stones than the opponent as possible. 
　　Now Alice gets the first turn, and she wants to know, if both of them act the optimal way, what will be the difference between the number of her Magic Stones and the number of Bob's Magic Stones at the end of the game.

Input

　　There are several cases(<=20). 
　　In each case, there are three integers at the first line: G, B, and S. Their meanings are mentioned above. 
　　Then B lines follow. Each line describes a bag in the following format: 
　　 
　　n c 1 c 2 ... c n 
　　 
　　It means that there are n Gems in the bag and their colors are color c 1,color c2...and color c n respectively. 
　　 0<=B<=21, 0<=G<=8, 0<n<=10, S < 20. 
　　There may be extra blank lines between cases. You can get more information from the sample input. 
　　The input ends with G = 0, B = 0 and S = 0.

Output

　　One line for each case: the amount of Alice's Magic stones minus the amount of Bob's Magic Stones.

Sample Input

3 4 3
2 2 3
2 1 3
2 1 2
3 2 3 1

3 2 2
3 2 3 1
3 1 2 3

0 0 0

Sample Output

3
-3

 题意：给你B个袋子，袋子里面有一些颜色不同的石头，一共有G种不同的的颜色，两人轮流挑选一袋石头全部放进cooker里，只要有一种颜色的石头的个数大于等于S，那么每S个这种颜色的石头就会变成一个魔法石，如果当前turn获得了一个或者多个魔法石，这个人就会有一个bonus turn，多玩一轮，问如果Alice先手，两人都用最优策略，最后Alice获得的魔法石的个数减去Bob获得的魔法石的个数。

题解：由于背包的数量不多，可以状压来优化，比如一共有四个袋子，如果状态为 0 0 0 0  那么所有的袋子都拿完了，没有任何魔法石个数的增加了，游戏结束；或者状态为  1 0 0 0   意思是第一个袋子没被拿，那么有人拿走之后，cooker里面的每个颜色的石头的个数就会增加，如果超过S那么魔法石的个数就会+1，还会获得一个额外的一轮。

再比如1 1 0 0状态，Alice 拿走了 第一个袋子，魔法石的个数增加了cnt个，并且又获得了一轮，那么下一个状态就是0 1 0 0 ，Alice的收益就是 cnt+dp[0100]；（懂了吗，嘿嘿）

具体细节看代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 1<<29
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int c[25][25];//每个袋子中每种石头颜色的个数
int cooker[21];//盘子里 每种颜色的石头的个数
int tem[21];//当前处理时的每种颜色的石头的个数
int dp[1<<22];//dp数组存下所有状态
int main()
{
    int G,B,S;
    while(scanf("%d%d%d",&G,&B,&S)==3&&G&&B&&S)
    {

        memset(c,0,sizeof(c));
        for(int i=0;i<B;i++)
        {
            int n;
            scanf("%d",&n);
            for(int j=0;j<n;j++)
            {
                int x;
                scanf("%d",&x);
                c[i][x]++;
            }
        }
        dp[0]=0;//袋子全为空的时候收益为零;
        int V=1<<B;
        for(int i=1;i<V;i++)
        {
            dp[i]=-inf;
            memset(cooker,0,sizeof(cooker));
            for(int j=0;j<B;j++)
            {
                if( !(i&(1<<j)))
                {
                    for(int k=1;k<=G;k++)
                    {
                        cooker[k]+=c[j][k];
                        while(cooker[k]>=S)cooker[k]-=S;
                    }
                }
            }
            for(int j=0;j<B;j++)
            {
                if((i&(1<<j)))
                {
                    int get=0;
                    for(int k=1;k<=G;k++)tem[k]=cooker[k];
                    for(int k=1;k<=G;k++)
                    {
                        tem[k]+=c[j][k];
                        while(tem[k]>=S)
                        {
                            tem[k]-=S;
                            get++;
                        }
                    }
                    if(get>0)dp[i]=max(dp[i],get+dp[i^(1<<j)]);
                    else     dp[i]=max(dp[i],0 - dp[i^(1<<j)]);
                }
            }
        }
        printf("%d\n",dp[V-1]);
    }
    return 0;
}