Các nhà khoa học đã phát hiện ra một số vi khuẩn lạ trên sao Hỏa và hiện đang bận rộn nghiên cứu chúng. Họ nhận thấy rằng số lượng vi khuẩn là lũy thừa của ~2~, vì mỗi vi khuẩn trên Sao Hỏa phân tách thành hai vi khuẩn mới (chết trong quá trình này) và tất cả đều bắt đầu từ một vi khuẩn duy nhất. Vì vậy, ở thế hệ đầu tiên chỉ có một loại vi khuẩn. Nó phân tách thành hai vi khuẩn thuộc thế hệ thứ hai, sau đó phân chia thành bốn vi khuẩn thuộc thế hệ thứ ba, v.v. – cho đến vi khuẩn ~2^K~ thuộc thế hệ ~K+1~ mà các nhà khoa học đã phát hiện ra. Họ đã đánh số vi khuẩn bằng cách sử dụng các số từ ~1~ đến ~2^K~ theo cách sau:

• Con của vi khuẩn ~(K)~ thế hệ trước theo thứ tự sau: ~\{1, 2\}, \{3, 4\}, \{5, 6\},..., \{2^K - 1, 2^K\}~
• Con của vi khuẩn ~(K-1)~ thế hệ trước theo thứ tự sau: ~\{1, 2, 3, 4\}, \{5, 6, 7, 8\}, ..., \{2^K - 3, 2^K - 2, 2^K - 1, 2^K \}~
• Con của vi khuẩn ~(K-2)~ thế hệ trước theo thứ tự sau: ~\{1, 2, 3, 4, 5, 6, 7, 8\}, ..., \{2^K - 7, 2^K - 6, 2^K - 5, 2^K - 4, 2^K - 3, 2^K - 2, 2^K - 1, 2^K \}~
• …
• Con của vi khuẩn thế hệ thứ hai theo thứ tự sau: ~\{1, 2, ..., 2^{K-1} \}~ và ~\{2^{K-1} + 1, 2^{K-1} + 2, ..., 2^K \}~

Trong đó dấu ngoặc nhọn biểu thị một tập hợp con cháu của một vi khuẩn. Nghĩa là, vi khuẩn ~2^K~ của thế hệ hiện tại được đánh số sao cho hậu duệ của bất kỳ vi khuẩn cũ nào có số lượng liên tiếp.

Lưu ý rằng tồn tại nhiều hoán vị khác nhau của những vi khuẩn này nhưng vẫn thỏa mãn quy luật rằng hậu duệ của bất kỳ vi khuẩn cũ nào cũng có số thứ tự liên tiếp. Các nhà khoa học muốn sắp xếp vi khuẩn thành một chuỗi có độ dài tối thiểu có thể. Độ dài của chuỗi vi khuẩn là tổng khoảng cách giữa tất cả các cặp vi khuẩn lân cận.

Cụ thể, có một lực đẩy nhất định có thể định lượng được giữa mỗi hai vi khuẩn, đó là khoảng cách tối thiểu giữa chúng nếu chúng ở cạnh nhau trong chuỗi. (Lực đẩy không đóng vai trò gì giữa các vi khuẩn không ở ngay cạnh nhau trong chuỗi.) Cho các giá trị lực đẩy của tất cả các cặp vi khuẩn, hãy tìm độ dài tối thiểu có thể có của chuỗi vi khuẩn (hoán vị) thỏa mãn quy tắc con cháu nêu trên.

Input

• Dòng đầu tiên chứa số nguyên dương ~K (1 ≤ K \le 9)~ từ câu lệnh bài toán.
• Mỗi dòng trong số ~2^K~ dòng tiếp theo chứa ~2^K~ số nguyên trong khoảng ~[0, 10^6]~. Các số ~2^K × 2^K~ này biểu thị lực đẩy giữa các cặp vi khuẩn: số ở hàng ~m~ và cột ~n~ là lực đẩy giữa vi khuẩn ~m~ và ~n~. Số này tất nhiên sẽ bằng số ở hàng ~n~ và cột ~m~. Với ~m = n~ số sẽ là ~0~.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa độ dài tối thiểu có thể có của chuỗi vi khuẩn thỏa mãn các ràng buộc.

Sample Input 1

2
0 7 2 1
7 0 4 3
2 4 0 5
1 3 5 0

Sample Output 1

13

Sample Input 2

3
0 2 6 3 4 7 1 3
2 0 7 10 9 1 3 6
6 7 0 3 5 6 5 5
3 10 3 0 9 8 9 7
4 9 5 9 0 9 8 4
7 1 6 8 9 0 8 7
1 3 5 9 8 8 0 10
3 6 5 7 4 7 10 0

Sample Output 2

32