P2473 [SCOI2008] Bonus Stage

You are playing your favorite video game and have just entered a bonus stage. In this stage, the system will randomly drop items $k$ times in sequence. Each time, you may choose to take the item or not take it (you must decide before the next drop, and an item you skip now cannot be taken later). There are $n$ types of items. Each drop is equally likely to be any of the $n$ types, and all drops are independent. That is, even if the system drops item $1$ in the first $(k - 1)$ drops (which is possible, though very unlikely), the probabilities for the $k$-th drop are still all $\frac 1 n$. Taking an item of type $i$ yields $p_i$ points, but not every item can be taken freely. Item $i$ has a prerequisite set $s_i$. You can take item $i$ only if every item in $s_i$ has been taken at least once. If the system drops an item that you currently cannot take, that opportunity is simply lost. Note that $p_i$ can be negative; however, if it is a prerequisite for many high-scoring items, taking this negative item at a short-term loss may lead to greater long-term gain. Assuming you follow the optimal strategy, what is the expected total score you can obtain in the bonus stage?

The first line contains two integers, the number of drops $k$ and the number of item types $n$. Lines $2$ through $(n + 1)$ describe the $n$ items. On line $(i + 1)$, several integers describe item $i$: first an integer $p_i$, then several distinct integers giving the prerequisites $s_i$, and finally an integer $0$ marking the end of the line.

Output a single real number, the answer, with six digits after the decimal point.

#### Constraints For all test points, it is guaranteed that $1 \leq k \leq 100$, $1 \leq n \leq 15$, and $-10^6 \leq p_i \leq 10^6$. Translated by ChatGPT 5