待ち伏せていた敵を見事撃破したうさぎは, 主人公を敵の城内に進めることに成功した. 主人公が城の地下牢に捕らわれていたねこたちを解放したところ, 彼らのうちの何匹かが主人公の力になってくれることになった.
ねこたちの話では, 城の奥にいる魔王に辿りつくには1 番からn 番のn 個の部屋をこの順に通り抜けることになるが, 各部屋には1 体ずつ敵が待ち受けていて逐一倒していかなければならないという. 仲間になったm匹のねこそれぞれについて, 各部屋の敵それぞれに対する勝率が分かっており, 主人公はこのねこたちを1 匹ずつ城の奥へ向けて派遣する. 各部屋はそこにいる敵を倒してからでなければ通過できないので, あるねこがある部屋の敵にやられたら, 次のねこはその部屋の敵から戦っていくことになる.
派遣されたねこは敵にやられるまで進むが, 派遣したねこがどの部屋の敵にやられたかは毎回知ることができ, それによって次にどのねこを派遣するかを決めることができる. どのようにすれば, ねこたちが待ち受けるすべての敵を倒せる確率が最大になるだろうか.
入力の一行目にはm とn がスペースで区切られて与えられる. 1 ≤ m, n ≤ 16
つづくm 行には, 猫が敵に勝つ確率を表すn 個の実数が与えられる. i + 1 行目のj 個目の実数は, j 番の部屋の敵に勝つ確率を表している. 確率は小数点以下3 桁まで.
ねこたちが待ち受けるすべての敵を倒せる確率が最大になるようにうまく順番を決めていくとき, その確率を答えよ. 出力は誤差を含んでいてもよいが, 真の値との誤差は10−9 以内にせよ.
2 3 0.900 0.500 0.100 0.500 0.500 0.500
0.372500000000