题目背景

玛雅有一个神奇的矩阵玩具。矩阵中的每个格子都由一次独立的随机实验决定：它可能显示为 1，也可能显示为 0。

玛雅想判断矩阵中是否存在一整列全部为 1。然而，查看一个格子的真实取值需要付出一次检查代价。为了尽可能节省检查次数，她希望预先安排一个最优的检查顺序。

请计算，在最优检查顺序下，为确定答案所需检查次数的最小期望值。

题目描述

给定一个包含 $n$ 行、$m$ 列的随机矩阵。

矩阵中第 $r$ 行、第 $c$ 列的元素记为：

$$a_{r,c}.$$

该元素是一个伯努利随机变量：

• 以 $p_{r,c}\%$ 的概率等于 1；
• 以 $(100-p_{r,c})\%$ 的概率等于 0。

所有 $n\times m$ 个随机变量相互独立。

一开始，玛雅不知道任何格子的实际取值。检查任意一个尚未得知的格子需要付出单位代价 $1$，并会得知该格子的实际值。

在检查开始之前，玛雅必须选定矩阵所有 $n\times m$ 个格子的一个排列，作为固定的检查顺序。

执行检查时遵循以下规则：

1. 玛雅按照预先选定的顺序依次考虑各个格子；
2. 如果某一列中已经检查出至少一个 0，则该列剩余的格子都不再检查；
3. 如果已经确认某一列的全部 $n$ 个格子都是 1，则立即停止检查，因为已经确定矩阵中存在全 1 列；
4. 如果每一列都已经检查出至少一个 0，则立即停止检查，因为已经确定矩阵中不存在全 1 列。

请在所有可能的固定检查顺序中，求实际检查次数的最小期望值。

输入格式

第一行包含两个整数 $n,m$，分别表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数。

第 $r$ 行的第 $c$ 个整数为 $p_{r,c}$，表示格子 $a_{r,c}$ 等于 1 的概率百分数。

输出格式

输出一个实数，表示最优检查顺序下的最小期望检查次数。

当你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$ 时，视为正确。

数据范围

对于所有测试数据：

• $1\le n\le 10$；
• $1\le m\le 250$；
• $1\le p_{r,c}\le 99$；
• 所有矩阵元素相互独立。

样例 1

输入

1 1
50

输出

1.0

解释

矩阵只有一个格子，无论其概率是多少，都必须检查一次。

样例 2

输入

2 2
50 50
50 50

输出

2.625

样例 3

输入

2 3
1 1 1
1 1 1

输出

3.0296970101000005

样例 4

输入

2 2
60 70
90 80

输出

2.382

解释

各格子为 1 的概率分别为：

$$p_{1,1}=60\%,\quad p_{1,2}=70\%,\quad p_{2,1}=90\%,\quad p_{2,2}=80\%.$$