ZOJ Problem Set - 3040
You may know, murphy have reduced Fan's RP. But he is still in angry and he want to beat Fan. Fan knows it , so he want to protect himself. It is known that murphy have N(<=50) weapons and Fan have M(<=50) shields. After hacking God's computer (You're familar with it, yes?), you know the probability that each weapons can attach each shield successfully. Since Fan's RP have been reduced, his IQ is also very low. Murphy never know Fan's strategy (You can never imagine a silly people's behavior) and Fan can't know Murphy's strategy neither (Because he is silly^_^). But Murphy is very clever, so he will choose his strategy carefully, to make his win probability maximum whatever Fan's choice is. And he want you to tell him the probability that he will win(Because he is busy prepering his weapons).
The first line is number of cases(<=50). Each case start with N and M. N line follows, each contain M numbers, where the j-th integer represents the percent probability that Murphy will win if weapon i is used by Murphy and shield j is used by Fan.Output
One line for each case, the probability.
1 2 2 50 80 60 30
Murphy can use weapon 1 and 2 at the probability 50%. If Fan use shield 1, Murphy have 50%*50+50%*60=55% to win. If Fan use shield 2, Murphy have 50%*80+50%*30=55% to win. So the answer is 55%.
Author: SHANG, Zechao
Source: ZOJ Monthly, September 2008