Phiếu dự đoán giải đấu

Một giải đấu loại trực tiếp có $2^N$ đội, đánh số từ $1$ đến $2^N$. Giải kéo dài $N$ vòng, mỗi vòng loại đi một nửa số đội.

Vòng $1$ gồm $2^{N-1}$ trận, đánh số từ $1$. Ở trận thứ $i$ của vòng $1$, đội $2i-1$ gặp đội $2i$. Đội thua bị loại, đội thắng đi tiếp (không có trận hòa). Mỗi vòng tiếp theo có số trận bằng một nửa vòng trước: ở trận thứ $i$ của vòng đó, đội thắng trận $2i-1$ gặp đội thắng trận $2i$ của vòng liền trước.

Bạn cần lập một phiếu dự đoán: với mỗi trận của giải, chọn ra một đội mà bạn dự đoán sẽ thắng. Ở vòng $1$ bạn được chọn tuỳ ý một trong hai đội của trận. Nhưng ở các vòng sau, đội mà bạn dự đoán thắng một trận bắt buộc phải là đội đã được bạn dự đoán thắng ở vòng liền trước. Toàn bộ phiếu được điền xong trước khi giải bắt đầu.

Mỗi dự đoán đúng ở vòng $1$ được $1$ điểm; dự đoán đúng ở mỗi vòng sau được số điểm gấp đôi vòng trước, nên dự đoán đúng trận chung kết được $2^{N-1}$ điểm.

Với mọi cặp đội, bạn đã ước lượng được xác suất thắng của mỗi đội nếu hai đội đó gặp nhau. Hãy lập phiếu dự đoán sao cho kỳ vọng số điểm đạt được là lớn nhất.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$.
• $2^N$ dòng tiếp theo, mỗi dòng chứa $2^N$ số nguyên. Số ở cột $j$ của dòng $i$ là xác suất (tính theo phần trăm) đội $i$ thắng đội $j$ nếu hai đội gặp nhau.

Dữ liệu ra

In ra kỳ vọng số điểm lớn nhất trên mọi phiếu dự đoán. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá ${10}^{-9}$.

Ràng buộc

• $2\le N\le 6$
• $0\le p_{i,j}\le 100$
• $p_{i,i}=0$
• $p_{i,j}+p_{j,i}=100$ với mọi $i\ne j$

Ví dụ