从前,有一位老人和他的妻子住在蔚蓝的海边。有一天,老人去钓鱼,钓到了一条真正的活金鱼。鱼说:“噢,老渔夫!请让我自由地进入大海,我会给你n件礼物,任何你想要的礼物!”。然后鱼给了老人一份礼物清单和价格。清单上的一些礼物可能名称相同但价格不同。但是,不能有两件具有相同名称和相同价格的礼物。此外,还可以有名称不同但价格相同的礼物。老人可以从列表中询问 n 个项目的名称。如果鱼的列表中有 p 次出现给定的名称,那么老人就不能询问该项目的名称超过 p 次。
老人知道,如果他要同名的礼物,鱼会随机(即在所有可能的选择中统一)从列表中选择同名的不同价格的礼物。老人想取悦他贪婪的妻子,所以他会选择n个名字,这样他就能以最高的价格得到n件礼物。况且他也不是最聪明的渔夫,所以如果有几种这样的方式,他统一选择其中一种。
老人想知道,他能得到n件最贵的礼物的概率是多少。由于老人不擅长概率论,所以他请你帮助他。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 1000) — 相应地,老人的愿望数量和金鱼列表中不同名称的数量。然后是 m 行:第 i 行首先包含整数 ki (ki > 0) — 第 i 个名称的礼物的不同价格数量,然后是 ki 个不同的空格分隔整数 cij (1 ≤ cij ≤ 109),即礼物的价格。
保证所有ki的总和不超过1000。保证n不大于礼物总数。
输出
在一行上打印一个实数——获得 n 个最有价值礼物的概率。如果答案的绝对误差或相对误差不超过 10 - 9,则认为答案是正确的。
示例
输入 #1
3 1 3 10 20 30
输出 #1
1.000000000
输入 #2
3 2 1 40 4 10 20 30 40
输出 #2
0.166666667