Paper Assembly with Category Constraints

Given a bank of n questions, where each question is associated with one or more categories, you are required to form a test paper by selecting m questions. In addition, the selected set must contain at least one question for each of a set of specified required categories.

More formally, each question has a set of categories. You are given a list of required categories \(R\). A valid paper is a set of \(m\) questions whose union of categories covers \(R\), i.e. for every \(r \in R\), there is at least one question in the paper whose category set contains \(r\).

Your task is to compute the number of valid paper assembly ways.

Input Format:
- The first line contains three integers \(n\), \(m\) and \(k\) where \(k\) is the number of required categories.
- The next \(n\) lines describe each question. Each line starts with an integer \(t\) denoting the number of categories for that question, followed by \(t\) integers representing the categories of the question.
- The last line contains \(k\) integers specifying the required categories.

Output Format:
Output a single integer, the number of ways to select \(m\) questions that satisfy the requirement.

Note: If needed, you may assume that \(n\) is small enough so that a dynamic programming solution is feasible.

inputFormat

The input is given as follows:

 n m k
 t1 c11 c12 ... c1t1
 t2 c21 c22 ... c2t2
 ...
 tn cn1 cn2 ... cntn
 r1 r2 ... rk

Where:

• n is the number of questions.
• m is the number of questions to select.
• k is the number of required categories.
• For each question, ti is the number of categories associated with that question followed by ti integers specifying the categories.
• The final line contains k integers representing the required categories.

outputFormat

Output a single integer denoting the number of valid ways to assemble a paper under the given requirements.

sample

3 2 1
1 1
1 2
2 1 2
1

3