CF859D.Third Month Insanity

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.

一年一度的大学体育球类锦标赛即将拉开帷幕，出于商标原因，我们将其称为“三月疯狂”（Third Month Insanity）。共有 $2^N$ 支队伍参赛，编号为 $1$ 至 $2^N$。锦标赛共进行 $N$ 轮，每轮淘汰一半的队伍。第一轮共进行 $2^{N-1}$ 场比赛，编号从 $1$ 开始。在第 $i$ 场比赛中，队伍 $2\cdot i - 1$ 将对阵队伍 $2\cdot i$。负者被淘汰，胜者晋级下一轮（比赛无平局）。后续每轮的比赛场数均为前一轮的一半；在第 $i$ 场比赛中，上一轮第 $2\cdot i - 1$ 场比赛的胜者将对阵上一轮第 $2\cdot i$ 场比赛的胜者。

每年办公室都会组织竞猜活动，看谁能设计出最优的预测对阵表（bracket）。一份对阵表即是对每场比赛获胜方的完整预测集合。对于第一轮的比赛，你可以任意预测任一参赛队获胜；但对于后续轮次的比赛，你所预测的胜者，必须也在前一轮中被你预测为胜者。注意：该对阵表需在任何实际比赛开始前就完全确定。首轮预测正确得 $1$ 分；此后每轮预测正确的得分均为前一轮的两倍，因此决赛（第 $N$ 轮唯一一场比赛）预测正确可得 $2^{N-1}$ 分。

对于联盟中每一对队伍，你均已估算出：若二者交锋，各自获胜的概率。现在，你希望构造一份期望总分最大的对阵表。

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.

输入的第一行包含一个整数 $N$（$2 \leq N \leq 6$）。

接下来有 $2N$ 行，每行包含 $2N$ 个整数。第 $i$ 行第 $j$ 列的数值表示队伍 $i$ 击败队伍 $j$ 的百分比概率；当 $i = j$ 时，该值为 $0$。保证第 $j$ 行第 $i$ 列的数值与第 $i$ 行第 $j$ 列的数值之和恰好为 $100$。

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 .

输出所有可能括号序列中最大的期望得分。你的答案必须在绝对或相对误差 $10^{-9}$ 范围内正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。若满足
，
则你的答案被视为正确。

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.

在第一个示例中，您应预测第 1 队和第 4 队在第 1 轮获胜，并预测第 1 队在第 2 轮获胜。请注意：您在第 2 轮预测的获胜队伍，也必须在第 1 轮被预测为获胜队伍。