Problem Description

You are playing your favorite video game and have just entered a reward round. In this round, the system will randomly drop treasures $k$ times in sequence. Each time, you can choose to take or not take the treasure (you must make the decision before the next treasure is dropped, and treasures you decide not to take cannot be taken later).

There are $n$ types of treasures, and the system has an equal and independent probability of dropping any of these $n$ types each time. That is, even if the system has dropped treasure $1$ for the first $(k-1)$ times (this is possible, although the probability is very small), the probability of dropping each type of treasure in the $k$-th round is still $\frac{1}{n}$.

Taking the $i$-th type of treasure will earn you $p_i$ points, but not all treasures can be taken freely. The $i$-th type of treasure has a prerequisite set $s_i$. You can only take the $i$-th type of treasure if you have taken all the treasures in the set $s_i$ at least once (if the system drops a treasure you cannot take, it means you lose the opportunity). Note that $p_i$ can be negative, but if it is a prerequisite for many high-scoring treasures, taking this negative-scoring treasure will result in greater long-term benefits by sacrificing short-term interests.

Assuming you adopt the optimal strategy, what is the average score you can obtain in the reward round?

Input Format

The first line contains two integers, representing the number of times treasures are dropped $k$ and the number of types of treasures $n$.

From the second to the $(n + 1)$-th line, each line contains several integers describing the information of the $i$-th treasure. The first integer on each line represents the score $p_i$ of the $i$-th treasure. Following are several distinct integers representing the prerequisite set $s_i$ of the treasure, ending with an integer $0$ indicating the end of the line.

Output Format

Output a single line with a real number representing the answer, rounded to six decimal places.

Sample Input and Output

Input Sample #1

1 2
1 0
2 0

Output Sample #1

1.500000

Input Sample #2

6 6
12 2 3 4 5 0
15 5 0
-2 2 4 5 0
-11 2 5 0
5 0
1 2 4 5 0

Output Sample #2

10.023470

Notes

Data Size and Constraints

For all test cases, it is guaranteed that $1 \leq k \leq 100$, $1 \leq n \leq 15$, and $-10^6 \leq p_i \leq 10^6$.

见题面 Input 部分

见题面 Output 部分