Another Sith Tournament

你是一位骑士，与其他n-1个骑士同时爱上了LKJ，所以你们不得不通过决斗的方式来选出谁能最终得到LKJ。 幸运的是你知道任意骑士i击败骑士j的概率，你还被推选为组织委员。决斗一开始你需要任意选择两名骑士（包括自己）进行决斗，胜利方继续和你另外选择的一名骑士决斗，直到仅剩一人，最终的胜利者将得到LKJ。 你非常渴望取得胜利，想知道自己得到LKJ的最大概率是多少，注意你是1号。 ------------ 第一行一个正整数$n$，表示一共有$n$名骑士。 接下来是一个$n * n$的实数矩阵，$A_{ij}$ 表示$i$战胜$j$的概率。 保证$ A_{ii} $为 0，且 $A_{ij}+A_{ji}=1$ ------------ 输出一个数，表示你得到LKJ的概率，误差在$10^{-6}$以内。

The rules of Sith Tournament are well known to everyone. $ n $ Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive. Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.

The first line contains a single integer $ n $ ( $ 1<=n<=18 $ ) — the number of participants of the Sith Tournament. Each of the next $ n $ lines contains $ n $ real numbers, which form a matrix $ p_{ij} $ ( $ 0<=p_{ij}<=1 $ ). Each its element $ p_{ij} $ is the probability that the $ i $ -th participant defeats the $ j $ -th in a duel. The elements on the main diagonal $ p_{ii} $ are equal to zero. For all different $ i $ , $ j $ the equality $ p_{ij}+p_{ji}=1 $ holds. All probabilities are given with no more than six decimal places. Jedi Ivan is the number $ 1 $ in the list of the participants.

Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed $ 10^{-6} $ .

3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0

0.680000000000000