B3618 寻找团伙
题目描述
世界局势风云变幻,你想办一件大事。办事自然要有人参与,你能从 $n$ 个人里面挑选一部分人共襄盛举。
要办这件事,一共涉及 $k$ 方面的能力,例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力,例如机器猫就可能擅长睡觉、擅长玩游戏,而不擅长游说他人。
你的计划很宏伟,因此你希望团队拥有很全面的能力。不幸的是,如果团队中有偶数个人拥有同一类能力,那么他们就会分成两派,争执不下,导致整个团队丧失这方面的能力。相应地,如果这项能力只有奇数个人拥有,那么他们总能形成一个多数派,帮团队去做这方面的工作。
需要注意的是,团队拥有的每一项能力,对计划的成功率的贡献是不一样的。第一项能力最重要,它的权重是 $2^{k-1}$;第二项能力的权重是 $2^{k-2}$;依次类推。第 $k$ 项能力最不重要,权重只有 $1$。
计划的成功率得分,即是**团队拥有的所有能力对应的权重之和**。
你希望计划成功率最大。因此,你需要选出合适的人士,来参与到你的宏图伟业中。
输入格式
第一行,两个正整数 $n, k$。分别表示供你挑选的人的数量,以及能力的种类数。
接下来 $n$ 行,每行表示每个人拥有的能力。这一行首先有一个整数 $c$,表示该人士拥有多少种能力;接下来是 $c$ 个 $[1, k]$ 之间的正整数,表示该人士拥有哪些能力。
输出格式
仅一行,一个整数,表示计划的成功率得分。
说明/提示
#### 样例解释
第一组样例,共 5 个人,每个人拥有的能力不一样。最终选择的结果是让这 5 个人都参与计划,得分 $16+8+4+2+1 = 31$。
第二组样例,我们选择只让 $1$ 参与。那么团队具有能力 $1,2, 3$,得分 $16+8+4=28$。
第三组样例,我们让 $1,2,3$ 参与。由于团队中有偶数个成员拥有能力 $5$,故团队并不拥有能力 $5$。奇数个成员拥有能力 $2$,故团队拥有能力 $2$。最终,团队具有能力 $1,2,3,4$。得分 $16+8+4+2=30$。
#### 数据规模与约定
对于 $100\%$ 的数据,有 $n\leq 21, k\leq 60$。