Optimal Treasure Collection

You are playing your favorite video game and have just entered a reward round. In this round, the system will randomly throw $k$ treasures one after another. For each treasure thrown, you must decide whether to eat it immediately or to skip it (if you skip it now, you can never eat it later, even if it appears again).

There are $n$ types of treasures. In each throw, every one of the $n$ treasure types appears with equal probability $\frac{1}{n}$, independently of previous throws. That means even if the first $(k-1)$ throws all give you treasure type 1 (a very unlikely event), the $k$-th throw still gives each treasure type with probability $\frac{1}{n}$.

Collecting a treasure of type $i$ gives you $p_i$ points. However, not every treasure type can be collected freely. Each treasure type $i$ has a prerequisite set $s_i$. You can only eat a treasure of type $i$ if you have already eaten every treasure in $s_i$ at least once. (If the system throws a treasure that you cannot eat at the time due to missing prerequisites, that throw is wasted.) Note that $p_i$ can be negative. In such cases, you might decide to eat a negative-score treasure in order to satisfy prerequisites for many high‐score treasures later.

Assuming you adopt an optimal strategy, what is the expected total score you will obtain in the reward round?

inputFormat

The first line contains two integers $n$ and $k$, where $n$ is the number of treasure types and $k$ is the number of throws.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$, where $p_i$ is the score gained by collecting treasure type $i$.

Then follow $n$ lines. The $i$-th of these lines describes the prerequisite set for treasure type $i$. Each such line begins with an integer $m_i$, the number of treasures in $s_i$, followed by $m_i$ distinct integers indicating the treasure types that are prerequisites for type $i$. Treasure types are numbered from 1 to $n$.

outputFormat

Output a single number, the expected total score you will obtain if you take the optimal strategy. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

sample

2 3
1 2
0
1 1

1.875000