问题文

高桥君非常喜欢收集偶像卡牌游戏。
在这个游戏中，通过支付一定金额来抽取抽奖，可以得到一个由某种概率分布决定的偶像。
高桥君想要收集所有的偶像。
有 M 种不同的抽奖方式，每种抽奖方式中，每个偶像的出现概率以及一次抽奖所需要的费用都不同。
如果高桥君采取最优策略来收集所有的偶像，求所需费用的期望值。

---

输入

输入从标准输入中以以下格式给出：N M C1 cost1 idol1,1 p1,1 idol1,2 p1,2 : idol1,C1 p1,C1 : CM costM idolM,1 pM,1 idolM,2 pM,2 : idolM,CM pM,CM

1. 第 1 行为两个整数 N(1≤N≤10) 和 M(1≤M≤4)，分别表示偶像总数和抽奖方式数，两个数以半角空格分隔。
2. 接下来的第 2 行到第 M+1 行，每行描述一个抽奖方式的信息，每行信息以半角空格分隔。

• 整数 C_i (1≤C_i≤N) 表示第 i 种抽奖方式中包含的偶像数量。
• 整数 cost_i (1≤cost_i≤3000) 表示一次抽奖所需费用。

4. 在第 M+2 行到第 2+M+C_1+C_2+...+C_M 行之间，描述了每种抽奖方式中包含的偶像信息。

• 整数 idol_{i,j} (1≤idol_{i,j}≤N) 表示第 i 种抽奖方式中包含的第 j 个偶像。
• 整数 p_{i,j} (1≤p_{i,j}≤100) 表示第 i 种抽奖方式中包含的第 j 个偶像的出现概率（百分率表示）。
• 第 i 种抽奖方式中包含的所有偶像的出现概率之和为 100。

部分分

此问题设置了部分得分。

• 当满足 N=1 且 M=1 的所有输入时，获得 10 分。
• 当满足 N=1 的所有输入时，额外获得 10 分。
• 当满足 C_i=1 的所有输入时，额外获得 10 分。
• 当满足 N≤2 的所有输入时，额外获得 20 分。
• 当满足 M=1 的所有输入时，额外获得 20 分。
• 当对所有测试用例均正确时，额外获得 30 分，总分为 100 分。

输出

如果高桥君采取最优策略来收集所有的偶像，求所需费用的期望值。
如果绝对误差或相对误差中至少有一个小于 $10^{-6}$，则答案被认为是正确的。
注意，在输出的末尾加上换行符。

解决方法

如果您不知道如何解决此问题，本问题设置了很多部分得分。即使不知道能够获得满分的解法，也可以尝试提交只针对部分得分的代码。
另外，此问题的难度与 D 题相当。建议阅读两个问题并尝试理解解题思路。

---

输入示例 1

5 2
2 300
3 5
4 95
3 500
5 20
1 30
2 50

输出示例 1

9343.17042606516

• 偶像有 5 种，抽奖方式有 2 种。

1. 在第一种抽奖方式中，可以获得 2 种不同的偶像，每次需要花费 300 单位的费用。

• 第一种抽奖方式包含的第一个偶像是偶像 3，出现概率为 5%。
• 第一种抽奖方式包含的第二个偶像是偶像 4，出现概率为 95%。

3. 在第二种抽奖方式中，可以获得 3 种不同的偶像，每次需要花费 500 单位的费用。

• 第二种抽奖方式包含的第一个偶像是偶像 5，出现概率为 20%。

• 第二种抽奖方式包含的第二个偶像是偶像 1，出现概率为 30%。

• 第二种抽奖方式包含的第三个偶像是偶像 2，出现概率为 50%。

• 在这个输入示例中，两个抽奖方式都能够获得不同的偶像。

• 第一种抽奖方式需要的费用是 6015.789473684，第二种抽奖方式需要的费用是 3327.380952381，所以总共需要的费用是 9343.17042606516。

---

输入示例 2

3 3
1 10
1 100
1 10
2 100
1 10
3 100

输出示例 2

30

• 每种抽奖方式只抽取一次，就可以收集到所有的偶像。

---

输入示例 3

1 1
1 1000
1 100

输出示例 3

1000

• 因为只有一个偶像和一种抽奖方式，所以只需要抽一次就可以了。费用是 1000 单位。

---

输入示例 4

2 2
2 1000
1 30
2 70
2 800
1 80
2 20

输出示例