题目内容

小美是一个富有的商人，他在一家大型贸易公司工作。他的公司位于城市的中心区，是一座高耸的摩天大楼。他住在郊区的别墅，是一座豪华的欧式建筑。他每天都要开车上下班，穿越城市的繁华和拥堵。

不幸的是，这个城市为了缓解交通拥堵，实行了限行规则，每天都有一些车牌号的最后一位数字被禁止上路。

小美不想因为限行而迟到或者请假，因为他的工作很重要，涉及到很多国际贸易的合同和谈判。所以他想买几辆车，让他每天都有车可以用。

假设他不能换车牌号，也不能选择其他交通方式，而且他的工作时间是固定的，问他至少需要买多少辆车？如果没有办法做到，就输出 $−1$ 。

输入描述

输入一共有 $7$ 行，表示周一至周日的限行情况。

输入每一行，第 $i$ 行的第一个数字 $c_i$ 表示当天限行数字个数，随后输入 $c_i$ 个互不相同的数字，第 $j$ 个数字为 $a_{ij}$ ，表示限行数字。

对于所有的数据， $0\le c_i \le 10, 0\le a_{ij} \le 9$ 。

输出描述

输出为一个整数，表示小美需要的最少车辆数或小美不能保证每天都至少有一辆车可以出行。

样例

输入

8 0 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7 8
8 2 3 4 5 6 7 8 9
8 0 1 2 3 4 5 8 9
8 0 1 2 3 6 7 8 9
8 0 1 4 5 6 7 8 9
8 2 3 4 5 6 7 8 9

输出

5

样例解释

一种可能的方案是，选购最后车牌一位数字分别为 $0,2,4,6,8$ 的 $5$ 辆车，此时每天都有车辆可以出行。

题目思路

思路：二进制状态压缩

将车牌 $0$ 到 $9$ 分别看成 $2^0$ 到 $2^9$，即二进制表示十进制数的存在与否。如此 $[0, 1023]$ 就可以表示 $0$ 到 $9$ 是否存在了。

$bit_i$ 表示第 $i$ 天允许通行的车牌号。

所以只要枚举 $[1, 1023]$ 这些车牌号的状态表示，然后对满足任意一天都可以有车牌通行的所有车牌状态表示，计算这些状态表示的车牌的数量，并取个 $\min$ ，每辆车都有不同的车牌号，故这就是最少的车牌数量就是需要的车的数量。