UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2891. 匹配难题

Statistics 下载数据

Description

给定一个二分图a,b.每条a->b的边都有一个存在的概率。求期望最大匹配数。

Input

第一行两个整数a,b
接下来一个a*b的矩阵表示i->j这条边存在的概率。

Output

一个实数表示期望最大匹配数。保留2位小数(注意C++以及PASCAL对于四舍五入的问题,比如PASCAL对于2.5四舍五入会输出2,建议输出时加一个极小量)

Sample Input


3 3
0.38064 0.30000 0.29486
0.41715 0.90000 0.67837
0.53316 1.00000 1.00000
【输出样例】
2.575940


【输入样例】
2 2
0.40000 1.00000
0.10000 1.00000

Sample Output


1.46
【数据规模和约定】
10% a*b<=16

10% a = 1,b <= 100
10% a = 2,b <= 100
10% a = 3,b <= 100
20% a = 4,b <= 100
20% a = 5,b <= 100
20% a=6,b<=100

Hint

Source