The annual college sports-ball tournament is approaching, which for trademark reasons we'll refer to as Third Month Insanity. There are a total of 2_N_ teams participating in the tournament, numbered from 1 to 2_N_. The tournament lasts _N_ rounds, with each round eliminating half the teams. The first round consists of 2_N_ - 1 games, numbered starting from 1. In game _i_, team 2·_i_ - 1 will play against team 2·_i_. The loser is eliminated and the winner advances to the next round (there are no ties). Each subsequent round has half as many games as the previous round, and in game _i_ the winner of the previous round's game 2·_i_ - 1 will play against the winner of the previous round's game 2·_i_.
Every year the office has a pool to see who can create the best bracket. A bracket is a set of winner predictions for every game. For games in the first round you may predict either team to win, but for games in later rounds the winner you predict must also be predicted as a winner in the previous round. Note that the bracket is fully constructed before any games are actually played. Correct predictions in the first round are worth 1 point, and correct predictions in each subsequent round are worth twice as many points as the previous, so correct predictions in the final game are worth 2_N_ - 1 points.
For every pair of teams in the league, you have estimated the probability of each team winning if they play against each other. Now you want to construct a bracket with the maximum possible expected score.
## Input
Input will begin with a line containing _N_ (2 ≤ _N_ ≤ 6).
2_N_ lines follow, each with 2_N_ integers. The _j_\-th column of the _i_\-th row indicates the percentage chance that team _i_ will defeat team _j_, unless _i_ = _j_, in which case the value will be 0. It is guaranteed that the _i_\-th column of the _j_\-th row plus the _j_\-th column of the _i_\-th row will add to exactly 100.
## Output
Print the maximum possible expected score over all possible brackets. Your answer must be correct to within an absolute or relative error of 10 - 9.
Formally, let your answer be _a_, and the jury's answer be _b_. Your answer will be considered correct, if .
[samples]
## Note
In the first example, you should predict teams 1 and 4 to win in round 1, and team 1 to win in round 2. Recall that the winner you predict in round 2 must also be predicted as a winner in round 1.
Let $ N \in \mathbb{N} $, $ 2 \leq N \leq 6 $, and let $ T = 2^N $ be the number of teams, labeled $ 1, 2, \dots, T $.
Let $ P \in [0,1]^{T \times T} $ be a probability matrix where $ P[i][j] $ is the probability that team $ i $ defeats team $ j $, with $ P[i][i] = 0 $ and $ P[i][j] + P[j][i] = 1 $ for all $ i \ne j $.
The tournament has $ N $ rounds. In round $ r \in \{1, 2, \dots, N\} $, there are $ 2^{N - r} $ games.
In round 1, game $ i $ (for $ i = 1, \dots, 2^{N-1} $) is between teams $ 2i - 1 $ and $ 2i $.
In round $ r > 1 $, game $ i $ is between the winners of round $ r-1 $ games $ 2i - 1 $ and $ 2i $.
A **bracket** is a function $ B $ assigning to each game $ (r, i) $ a predicted winner $ B(r,i) \in \{1, \dots, T\} $, subject to the constraint:
For $ r \geq 2 $, the predicted winner $ B(r,i) $ must be one of the two teams predicted to win games $ (r-1, 2i-1) $ and $ (r-1, 2i) $.
The score for a correct prediction in round $ r $ is $ 2^{r-1} $ points.
Let $ W(r,i) $ be the actual winner of game $ (r,i) $, determined stochastically by the tournament outcomes and the probability matrix $ P $.
The **expected score** of bracket $ B $ is:
$$
\mathbb{E}[S(B)] = \sum_{r=1}^N \sum_{i=1}^{2^{N-r}} 2^{r-1} \cdot \mathbb{P}\left( B(r,i) = W(r,i) \right)
$$
The goal is to compute:
$$
\max_{B \in \mathcal{B}} \mathbb{E}[S(B)]
$$
where $ \mathcal{B} $ is the set of all valid brackets satisfying the constraint.
The tournament structure defines a complete binary tree of depth $ N $, with $ 2^N $ leaves (teams) and $ 2^N - 1 $ internal nodes (games). The bracket prediction corresponds to choosing, for each internal node, one of its two children as the predicted winner, with consistency: the winner chosen at a parent node must be one of the two winners chosen at its children.
Thus, the problem reduces to:
Given a complete binary tree of depth $ N $, with each leaf labeled by a team $ \in \{1,\dots,2^N\} $, and a pairwise win probability matrix $ P $, compute the maximum expected score over all consistent assignments of winners to internal nodes, where the score for assigning winner $ w $ to a node at depth $ r $ (root at depth 1) is $ 2^{r-1} \cdot \mathbb{P}(w \text{ wins the subtree rooted at this node}) $.
Define $ \text{dp}[v][w] $ as the maximum expected score obtainable in the subtree rooted at node $ v $, given that team $ w $ is predicted to win that subtree.
For a leaf node $ v $ corresponding to team $ t $, set $ \text{dp}[v][t] = 0 $ (no score from leaf; score comes from games).
For an internal node $ v $ at depth $ r $, with left child $ \ell $ and right child $ r $, and with predicted winner $ w $, we have:
$$
\text{dp}[v][w] = \max_{\substack{w_L \in \text{children}(\ell) \\ w_R \in \text{children}(r) \\ w \in \{w_L, w_R\}}} \left\{ \text{dp}[\ell][w_L] + \text{dp}[r][w_R] + 2^{r-1} \cdot \mathbb{P}(w \text{ beats } w' \mid w' \text{ is the other child}) \right\}
$$
where $ w' $ is the winner of the other child subtree.
But more precisely, since the winner of the subtree rooted at $ v $ must be one of the two winners of its children, and the probability that $ w $ wins the game at $ v $ depends only on the two teams that reach it, we can write:
Let $ \text{dp}[v][w] = \max_{\text{consistent assignments to subtree of } v \text{ with winner } w} \left( \text{expected score from subtree of } v \right) $
Then for internal node $ v $ at depth $ r $, with left child $ \ell $ and right child $ r $, and with possible winning teams $ L = \{ \text{teams that can win } \ell \}, R = \{ \text{teams that can win } r \} $, we compute:
$$
\text{dp}[v][w] = \max_{\substack{w_L \in L \\ w_R \in R \\ w \in \{w_L, w_R\}}} \left( \text{dp}[\ell][w_L] + \text{dp}[r][w_R] + 2^{r-1} \cdot P[w][w'] \right)
$$
where $ w' = w_R $ if $ w = w_L $, and $ w' = w_L $ if $ w = w_R $.
Base case: for leaf $ v $ corresponding to team $ t $, $ \text{dp}[v][t] = 0 $, and $ \text{dp}[v][w] = -\infty $ for $ w \ne t $.
The final answer is:
$$
\max_{w \in \{1,\dots,2^N\}} \text{dp}[\text{root}][w]
$$
The tree structure is fixed: the initial pairing is deterministic: in round 1, game $ i $ is between teams $ 2i-1 $ and $ 2i $, so the leaves are ordered as $ 1,2,3,4,\dots,2^N $, and the binary tree is built accordingly.
Thus, the problem is solvable via dynamic programming on the complete binary tree with $ 2^N - 1 $ internal nodes and $ 2^N $ leaves, with state $ \text{dp}[node][winner] $, and transitions as above.