Problem H
Diverse Contest

Write what you know! The judges for a certain programming competition have $n$ problems and are trying to prepare a contest using $k$ of them.

The judges have tagged each problem with a list of topics needed to solve that problem. To not overly punish teams for not knowing a specific topic, for any given topic, at most half of the problems on the contest can have that topic.

Compute the number of distinct contests the judges can prepare. Two contests are different if there is a problem that appears in one contest but not the other. In particular, the order of the problems in the contest does not matter.


The first line of input has two integers $n$ and $k$ where $n$ ($2 \leq n \leq 20$) is the number of proposed problems and $k$ ($2 \leq k \leq n$) is the number of problems that will be used in a contest. The next $n$ lines each begin with an integer $t$ ($1 \leq t \leq 20$), the number of topics for that problem. Then follow $t$ unique topics. Each topic is a string of lowercase letters, each of length at most $10$.


Output the number of distinct contests the judges can prepare.

Sample Input 1 Sample Output 1
5 3
1 string
2 string queue
1 queue
2 dp greedy
1 math

Please log in to submit a solution to this problem

Log in