The annual "Nongshim Cup" Three-Country Go Tournament is the highest-level Go competition in the world and the most exciting contest in the Go circles of China, Japan, and South Korea. This problem is based on the rules of this tournament.

The Three-Country Go Tournament is a competition between representative teams from three countries. The rules are briefly introduced as follows:

1. Let the three countries be $A$, $B$, and $C$. Each country has $n$ players (in the actual competition mentioned above, $n = 5$), referred to as $A_1, A_2, \dots, A_n$, $B_1, B_2, \dots, B_n$, and $C_1, C_2, \dots, C_n$.
2. Every match results in a win or a loss. The loser of each match is eliminated.
3. The first player to represent each team is fixed as the $n$-th player of that team, i.e., $A_n$, $B_n$, and $C_n$.
4. A team is selected by drawing lots with equal probability. This team receives a bye in the first round, while the $n$-th players of the remaining two teams play the first match.
5. The winner of the first match (the player who wins the game) plays the second match against the $n$-th player of the team that had the bye. For example, if $C_n$ defeats $A_n$ in the first match, then $C_n$ plays against $B_n$ in the second match.
6. Starting from the third match, the team that did not participate in the previous match selects an undefeated player to play against the winner of the previous match.
7. This process continues until all players of a certain team are eliminated.
8. When only two teams remain, after each match, the losing team chooses an undefeated player to play against the winner in the next match.
9. The competition ends when all players of any one of the two teams are eliminated. The remaining team wins the Nongshim Cup.

A new tournament is about to begin. As the team leader of team $A$, you have calculated the win rates between these $3n$ players before the start of the tournament—that is, for two players $Q$ and $R$ from different teams, we know the probability that $Q$ defeats $R$ is $p$ ($0 \le p \le 1$), and the probability that $R$ defeats $Q$ is $1 - p$.

Since your country is exceptionally strong, you can assume that the remaining two teams will both target you. The decisions of teams $B$ and $C$ (i.e., the order in which they send their players) are aimed at minimizing the probability that your country (team $A$) wins the championship, while the goal of team $A$'s decisions is to maximize the probability of winning the championship. Your task is to calculate the expected value $E_A$ of team $A$ winning the championship under these extremely unfavorable conditions, assuming all three parties make optimal decisions.

Regarding the calculation of expectation: Suppose the players currently on the field are $Q$ and $R$, and the probability that $Q$ defeats $R$ is $p$. Then the expected win rate for team $A$ at this moment is: $$E_A = p \times E_1 + (1 - p) \times E_2$$ where $E_1$ is the expected value of team $A$ winning the championship after $Q$ defeats $R$, and $E_2$ is the expected value of team $A$ winning the championship after $R$ defeats $Q$. $E_1$ and $E_2$ are calculated recursively using the same formula.

Team $A$'s decisions will try to make this expectation as large as possible, while teams $B$ and $C$ will try to make it as small as possible. When all players of teams $B$ and $C$ are eliminated, the winning expectation is 1; when all members of team $A$ are eliminated, the expectation is 0.

Input

The input file is go.in. The first line contains an integer $n$, representing the number of players per team. The second line to the $n+1$-th line each contain $n$ real numbers, forming an $n \times n$ matrix representing the win rates of team $A$ against team $B$. The $j$-th number in the $i+1$-th line represents the win rate of player $A_i$ against player $B_j$. The $n+2$-th line is an empty line. The $n+3$-th line to the $2n+2$-th line each contain $n$ real numbers, forming an $n \times n$ matrix representing the win rates of team $A$ against team $C$. The $j$-th number in the $i+n+2$-th line represents the win rate of player $A_i$ against player $C_j$. The $2n+3$-th line is an empty line. The $2n+4$-th line to the $3n+3$-th line each contain $n$ real numbers, forming an $n \times n$ matrix representing the win rates of team $B$ against team $C$. The $j$-th number in the $i+2n+3$-th line represents the win rate of player $B_i$ against player $C_j$.

Output

The output file go.out contains only one real number, rounded to 6 decimal places, representing the probability that team $A$ wins the championship.

Examples

Input 1

3
1.0 0.0 0.5
0.5 1.0 1.0
0.5 0.5 0.5
0.5 0.5 1.0
0.5 0.0 0.5
0.5 0.5 0.5
0.5 0.0 1.0
0.5 0.5 0.5
0.5 0.5 0.5

Output 1

0.273438

Constraints

• For 30% of the data, $n \le 4$.
• For 40% of the data, $n \le 5$.
• For 100% of the data, $n \le 7$.
• For 10% of the data, the three win rate matrices have identical elements within each matrix, but the values may differ between different matrices.