[SHOI2001]三国围棋对抗赛

题目背景

中国邀请韩国,日本围棋队来参加三国围棋对抗赛,韩国,日本应邀各派了5位超一流高手来参赛,中国围棋队希望能赢得这场比赛,但是这10位高手实力不俗。不过中国队作为东道主,可以在对方选手安排好出场顺序后再决定队员的组成以及出场顺序,以得到最大的获胜概率。

题目描述

比赛规则如下:先抽签决定第1轮轮空的队,由不轮空的2支队的1号队员进行比赛,失利的队员被淘汰,以后每次由前一轮获胜的队员与前一轮轮空的队剩下的队员中序号最小的队员进行比赛,直到只剩下一个国家的队员为止,这个国家就获得了比赛的胜利。

输入输出格式

输入格式


第1行为一个数n(5<=n<=15),中国队的候选人数。 接下来是n行,每行有10个数 第I+1行的10个数依次表示第I位中国选手对韩国1~5号,日本1~5号的胜率,胜率k(0<=k<=1)。 再接下来是5行,每行有5个数 第I+n+1行的第j个数表示韩国I号选手对日本j号选手的胜率。

输出格式


仅1行,为中国队的最大的获胜概率,保留6位小数。

输入输出样例

输入样例 #1

5
0.902 0.540 0.862 0.283 0.498 0.597 0.900 0.076 0.750 0.539 
0.342 0.574 0.743 0.442 0.579 0.502 0.755 0.649 0.835 0.278 
0.105 0.704 0.274 0.733 0.725 0.861 0.007 0.314 0.099 0.542 
0.785 0.754 0.541 0.331 0.430 0.426 0.928 0.385 0.314 0.892 
0.349 0.354 0.408 0.353 0.333 0.180 0.715 0.013 0.563 0.386 
0.131 0.564 0.265 0.700 0.033 
0.293 0.688 0.140 0.130 0.550 
0.346 0.915 0.385 0.536 0.946 
0.739 0.051 0.682 0.166 0.436 
0.122 0.065 0.724 0.934 0.736

输出样例 #1

0.529237