[SCOI2008]奖励关

你正在玩一款电子游戏，并进入了奖励关。在奖励关中，系统将依次随机抛出 $k$ 次宝物。每次抛出宝物后，你都可以选择吃或不吃，但必须在下一件宝物抛出前做出决定，且选择不吃的宝物之后不能再吃。

宝物共有 $n$ 种。每次抛出时，系统抛出每种宝物的概率均为 $\frac{1}{n}$ ，且各次抛出相互独立。即使前 $k-1$ 次抛出的都是第 $1$ 种宝物，第 $k$ 次抛出每种宝物的概率仍然均为 $\frac{1}{n}$ 。

吃掉第 $i$ 种宝物可以获得 $P_i$ 分，但并非所有宝物都能随意获取。第 $i$ 种宝物有一个前提宝物集合 $S_i$ ，只有当集合 $S_i$ 中的所有宝物都至少吃过一次时，才能吃掉第 $i$ 种宝物。如果系统抛出了一件当前不能吃的宝物，则这次机会会被浪费。

$P_i$ 可以为负数。但如果某件负分宝物是许多高分宝物的前提，那么牺牲短期利益吃掉它，可能会获得更大的长期收益。

请计算在采取最优策略的情况下，你在奖励关中能够获得的期望总分。

输入格式

第一行包含两个正整数 $k$ 和 $n$ ，分别表示系统抛出宝物的次数和宝物的种类数。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 种宝物。每行第一个整数为该宝物的分值 $P_i$ ，之后依次给出其所有前提宝物的编号，并以 $0$ 结尾。宝物编号为 $1$ 到 $n$ 。

输出一个实数，表示采取最优策略时能够获得的期望总分，保留 $6$ 位小数。

1 2
1 0
2 0

1.500000

本题为 SCOI 2008 试题「奖励关」，题面与测试数据整理自 BZOJ。

1 2
1 0
2 0

1.500000