Problem: 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 2N teams participating in the tournament, numbered from 1 to 2N. The tournament lasts N rounds, with each round eliminating half the teams. The first round consists of 2N - 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 2N - 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).

2N lines follow, each with 2N 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 <image>.

Examples

Input

2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0


Output

1.75


Input

3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0


Output

12


Input

2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0


Output

3.141592

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.

Solution (in JAVA):

Solution:
import java.awt.geom.Line2D;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.Collectors;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main2 {

    static int[][] probs;

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        int p = scanner.nextInt();
        int n = (int) Math.pow(2, p);
        probs = new int[n][];
        for (int i = 0; i < n; i++) probs[i] = scanner.nextIntArray(n);

        Round[] dp = new Round[n];
        for (int i = 0; i < n; i++) dp[i] = new Round(i);

        int point = 1;
        for (int i = 1; i <= p; i++) {
            Round[] nextdp = new Round[dp.length / 2];
            for (int j = 0; j < dp.length; j+=2) {
                Round first = dp[j];
                Round second = dp[j + 1];
                nextdp[j / 2] = first.mergeWith(second, point);
            }
            point *= 2;
            dp = nextdp;
        }
        DecimalFormat format = new DecimalFormat("0.000000000");
        System.out.println(dp[0].best(n / 2));
    }

    static class Round {
        Round left, right;

        double[] cache = new double[66];

        double[] probabs = new double[66];

        public Round(Round left, Round right, double[] probabs) {
            this.left = left;
            this.right = right;
            this.probabs = probabs;
        }

        public Round(int startFrom) {
            probabs[startFrom] = 1;
        }

        public Round mergeWith(Round with, int points) {
            double[] newProbabs = new double[66];
            for (int i = 0; i < 66; i++) {
                if (probabs[i] == 0) continue;

                for (int j = 0; j < 66; j++) {
                    if (with.probabs[j] == 0) continue;;

                    double p = probs[i][j] / 100.0;
                    double q = 1 - p;

                    newProbabs[i] += p * probabs[i] * with.probabs[j];
                    newProbabs[j] += q * probabs[i] * with.probabs[j];
                }
            }
            return new Round(this, with, newProbabs);
        }

        public double best(int score) {
            double max = 0;
            for (int i = 0; i < 66; i++) {
                if (probabs[i] > 0) max = Math.max(max, calc(i, score));
            }
            return max;
        }

        public double calc(int to, int score) {
            if (cache[to] != 0) return cache[to];

            double result = 0;
            Round ml = left;
            Round mr = right;

            if (left == null) {
                return probabs[to] * score;
            }

            if (left.probabs[to] == 0) {
                ml = right;
                mr = left;
            }
            double max = 0;
            for (int i = 0; i < 64; i++) {
                //if (i != to && i < probs[to].length && probs[to][i] > 0) {
//                if (Math.abs(mr.probabs[i] * ml.probabs[to] - probabs[to]) < 0.000001) {
                    max = Math.max(mr.calc(i, score / 2), max);
//                }
                //}
            }
            cache[to] =  probabs[to] * score + ml.calc(to, score / 2) + max;
            return cache[to];
        }
    }


    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
                throw new RuntimeException();
            }
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }

        long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) res[i] = nextLong();
            return res;
        }

        String[] nextStringArray(int n) {
            String[] res = new String[n];
            for (int i = 0; i < n; i++) res[i] = nextToken();
            return res;
        }
    }

    static class PrefixSums {
        long[] sums;

        public PrefixSums(long[] sums) {
            this.sums = sums;
        }

        public long sum(int fromInclusive, int toExclusive) {
            if (fromInclusive > toExclusive) throw new IllegalArgumentException("Wrong sum");
            return sums[toExclusive] - sums[fromInclusive];
        }

        public static PrefixSums of(int[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }

        public static PrefixSums of(long[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }
    }

    static class ADUtils {
        static void sort(int[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                int a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }

        static void sort(long[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                long a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }
    }

    static class MathUtils {
        static long modpow(long b, long e, long m) {
            long result = 1;

            while (e > 0) {
                if ((e & 1) == 1) {
            /* multiply in this bit's contribution while using modulus to keep
             * result small */
                    result = (result * b) % m;
                }
                b = (b * b) % m;
                e >>= 1;
            }

            return result;
        }
    }
}