#P1956. 宝石联盟

宝石联盟

yzwsm与Eric最近在玩一个的游戏----宝石联盟,游戏规则如下:

首先桌子上面有 B 个包裹,每个包裹中有一些宝石,每个宝石有一种颜色(我们事先将颜色编了号1,2,3... 最多 G 种颜色)。

然后yzwsm和Eric有一个反应堆,如果其中有S个宝石相同颜色,则这S个宝石会融合为一个魔法石,为自己积累能量。

现在yzwsm和Eric轮流在桌上挑选包裹(同一个包裹最多挑选一次),并获取里面的宝石放在反应堆中,由于反应中产生了魔法石将激发特殊奖励(也就是当前玩家有机会再挑选一个包裹,特殊奖励可无限连续激发)。

现在我们假设yzwsm先挑选,并且yzwsm与Eric都采用最优策略(使得自己最后的魔法石最多的策略)。问yzwsm获得的魔法石与Eric获得的魔法石的差是多少。

Input

每组数据(最多10组)
第一行三个整数 G B S
接下来 B 行每行 ni c1 c2 ... ci .. cni 其中第 i 行表示第 i 个包中的 ni 个宝石分别是哪些颜色
0 <= G <= 8, 0 <= B <= 20, S < 20,
1 <= n <= 10, 1 <= ci <= G
具体格式见样例

Output

一行一个整数输出答案

Sample Input

3 2 2
3 2 3 1
3 1 2 3

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

0 0 0

Sample Output

</p>
-3
3

HINT

Source