#2891. 匹配难题

内存限制:128 MiB 时间限制:10 Sec

题目描述

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

输入格式

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

输出格式

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

样例

样例输入


			

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

样例输出


			

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

数据范围与提示