Gifts

题目描述： 很久很久以前，一位老人和妻子住在海边。一天，他前去捕鱼，捉到了一条活着的金鱼。鱼说：“老渔人！我求你放我回到海里，我会给你$n$个礼物——任何你想要的礼物！”然后鱼给了老人一张礼物的清单并附上了礼物的价值。礼物可能有相同的名称、不同的价值，也可能会有不同的名称、相同的价值。然而，不会出现名称和价值都相同的礼物。老人可以要清单上的$n$个礼物。假设清单上共有 $p$ 样与该礼物名称相同的礼物（包括自身），则该礼物不能被索要超过 $p$ 次。 老人知道，如果他索要同一个名称的礼物$s$次，那么金鱼会等概率地随机选择该名称的$s$样礼物。为了满足他贪心的妻子，他会选择价值最高的$n$样礼物。此外，如果有不同的方法选择最高价值的$n$样礼物，他会等概率地采用其中任意一个方法。 老人想知道，他能拿到$n$样价值最高的礼物的概率是多少。由于他不擅长概率论，于是就来向你求助。 输入格式： 第一行有两个整数$n$和$m(1\leq n,m\leq1000)$，$n$为老人想要的礼物数量、$m$为清单上各不相同的名称的数量。 接下来有$m$行，第$i$行首先包括一个整数$k_i(ki> 0)$，代表第$i$个名称下礼物的数量。接着，$k_i$个各不相同的整数$c_{ij}(1\leq c_{ij}\leq10^9)$是这些礼物的价格。 输出格式： 输出仅一行：一个实数——老人拿到$n$样价值最高的礼物的概率。误差不超过$10^{-9}$时，输出被认为是正确的。

Once upon a time an old man and his wife lived by the great blue sea. One day the old man went fishing and caught a real live gold fish. The fish said: "Oh ye, old fisherman! Pray set me free to the ocean and I will grant you with $ n $ gifts, any gifts you wish!". Then the fish gave the old man a list of gifts and their prices. Some gifts on the list can have the same names but distinct prices. However, there can't be two gifts with the same names and the same prices. Also, there can be gifts with distinct names and the same prices. The old man can ask for $ n $ names of items from the list. If the fish's list has $ p $ occurrences of the given name, then the old man can't ask for this name of item more than $ p $ times. The old man knows that if he asks for $ s $ gifts of the same name, the fish will randomly (i.e. uniformly amongst all possible choices) choose $ s $ gifts of distinct prices with such name from the list. The old man wants to please his greedy wife, so he will choose the $ n $ names in such a way that he can get $ n $ gifts with the maximum price. Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly. The old man wondered, what is the probability that he can get $ n $ most expensive gifts. As the old man isn't good at probability theory, he asks you to help him.

The first line contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=1000 $ ) — the number of the old man's wishes and the number of distinct names in the goldfish's list, correspondingly. Then $ m $ lines follow: the $ i $ -th line first contains integer $ k_{i} $ $ (k_{i}&gt;0) $ — the number of distinct prices of gifts with the $ i $ -th name, then $ k_{i} $ distinct space-separated integers $ c_{ij} $ ( $ 1<=c_{ij}<=10^{9} $ ), the gifts' prices. It is guaranteed that the sum of all $ k_{i} $ doesn't exceed 1000. It is guaranteed that $ n $ is not greater than the total number of the gifts.

On a single line print one real number — the probability of getting $ n $ most valuable gifts. The answer will be considered correct if its absolute or relative error does not exceed $ 10^{-9} $ .

3 1
3 10 20 30

1.000000000

3 2
1 40
4 10 20 30 40

0.166666667