题目描述

中国邀请韩国、日本围棋队参加三国围棋对抗赛，每队各派 $5$ 位选手。中国作为东道主，可以在对方安排好出场顺序后，再决定自己的队员组成和出场顺序，以最大化获胜概率。

比赛规则：

1. 抽签决定第 $1$ 轮轮空的队
2. 由不轮空的两支队的 $1$ 号队员比赛，败者淘汰
3. 以后每轮由前一轮获胜的队员，与前一轮轮空队剩下的队员中序号最小的比赛
4. 直到只剩一个国家的队员，该国获胜

输入格式

• 第 $1$ 行：整数 $n$，中国候选人数
• 接下来 $n$ 行：每行 $10$ 个数，第 $i+1$ 行表示第 $i$ 位中国选手对韩国 $1 \dots 5$ 号、日本 $1 \dots 5$ 号的胜率
• 接下来 $5$ 行：每行 $5$ 个数，第 $i+n+1$ 行第 $j$ 个数表示韩国 $i$ 号对日本 $j$ 号的胜率

输出格式

一行，中国队最大获胜概率，保留 $6$ 位小数

样例

输入

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

输出

0.529237

数据范围与提示

对于 $100\%$ 的数据，$5 \le n \le 15$。

算法标签

动态规划，概率论，搜索