AT_arc016_3.[ARC016C] ソーシャルゲーム

高桥君非常喜欢玩偶像收集卡牌游戏。
在这个游戏中，通过支付一定金额进行抽奖，你可以根据某种概率分布来获得一名偶像。
高桥君的目标是收集到所有的偶像。
游戏中有 $M$ 种不同的抽奖方式，每种方式中的偶像出现概率和抽奖费用都不相同。
请你计算出高桥君要想获得所有偶像所需要的最小期望花费。输入如下格式：

$N$ $M$ $C_1$ $cost_1$ $idol_{1,1}$ $p_{1,1}$ $idol_{1,2}$ $p_{1,2}$ : $idol_{1,C_1}$ $p_{1,C_1}$ : $C_M$ $cost_M$ $idol_{M,1}$ $p_{M,1}$ $idol_{M,2}$ $p_{M,2}$ : $idol_{M,C_M}$ $p_{M,C_M}$

1. 第一行包含两个整数——$N (1 \le N \le 10)$和$M (1 \le M \le 4)$，分别表示偶像的总数和抽奖方式的数量。

2. 接下来的 $M$ 行每行描述一种抽奖方式的信息。

• 整数 $C_i$ 表示第 $i$ 种抽奖方式中偶像的数量。
• 整数 $cost_i$ 表示进行第 $i$ 种抽奖的费用。

5. 接下来，每个偶像信息包含两个整数 $(idol_{i,j}, p_{i,j})$，分别表示第 $i$ 种抽奖方式中第 $j$ 个偶像的编号以及出现的概率（百分比形式）。

• 每种抽奖方式中所有偶像的出现概率之和为 $100$。

请输出高桥君采用最优策略时，收集全部偶像所需的最小期望花费。结果的绝对误差或相对误差需小于 $10^{-6}$，结果最后附加换行。如你无从确定最佳策略，可尝试代码以获取部分分。

示例输入与输出

以下为几个例子以帮助理解这一任务：

输入：
5 2
2 300
3 5
4 95
3 500
5 20
1 30
2 50

输出：
9343.17042606516

在此例中，有 $5$ 种偶像和 $2$ 种抽奖方式。进行第 $1$ 种抽奖方式所需的期望费用为 $6015.789473684$，进行第 $2$ 种抽奖方式所需的期望费用为 $3327.380952381$，合计为 $9343.17042606516$。

输入：
3 3
1 10
1 100
1 10
2 100
1 10
3 100

输出：
30

该例子中，进行每种抽奖方式各一次即可收集完所有偶像。

输入：
1 1
1 1000
1 100

输出：
1000

由于只有一种偶像和一种抽奖方式，只需进行一次抽奖。

输入：
2 2
2 1000
1 30
2 70
2 800
1 80
2 20

输出：
2128.57142857143

• 第一行给出偶像的总数 $N$ 和抽奖方式的种类 $M$。

• 接下来的 $M$ 行中，每行描述一种抽奖方式的信息，依次为：

  • $C_i$，该种抽奖方式中所含偶像的数量。
  • $cost_i$，该种抽奖方式的费用。
  • 整数对列出该种抽奖方式中每个偶像的编号和其出现概率的百分比。

• 输出数字表示在采取最佳策略时收集所有偶像所需的最小期望花费。

• $1 \le N \le 10$
• $1 \le M \le 4$
• $1 \le C_i \le N$
• $1 \le cost_i \le 3000$
• 每种抽奖方式中所有偶像的出现概率之和为 $100$。

本翻译由 AI 自动生成