Migrated from Lutece 3147 集合的并

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定 $n$ 个集合，每个集合里的数都是 $[1,m]$ 内的整数，且每个集合的大小均为k。 请你选出 $n$ 个集合选出尽可能少的集合，使得这些集合的并集等于 $[1,m]$ 内的所有整数组成的集合，或者判断无法做到。

Input

第一行三个正整数 $n,m,k$ 接下来 $n$ 行每行 $k$ 个正整数 $a_1,a_2,...,a_k$ 代表集合里的元素

Output

如果有解，输出需要选出的最少集合个数 否则输出 -1

Samples

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

2

4 6 3
1 2 3
1 2 3
3 4 5
2 4 5

-1

Constraints

$1 \le n \le 100 , 1 \le k \le m \le 15 , 1 \le a_i \le m$

Note

样例解释 对于样例1，有若干中最优方案，其中一种为选择 {1，2，3} 与 {3，4，5} 两个集合，它们的并集为{1，2，3，4，5}。 对于样例2，没有一个集合内包含6，因此无法通过取并集得到{1，2，3，4，5，6} 。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming