Mars

Οι επιστήμονες ανακάλυψαν μερικά παράξενα βακτήρια στον Άρη και τώρα είναι απασχολημένοι με τη μελέτη τους. Παρατήρησαν ότι ο αριθμός των βακτηρίων είναι δύναμη του 2, αφού κάθε βακτήριο στον Άρη χωρίζεται σε δύο νέα βακτήρια (που πεθαίνουν στη διαδικασία) και όλα ξεκίνησαν από ένα μόνο βακτήριο.
Έτσι, στην πρώτη γενιά υπήρχε ένα μόνο βακτήριο. Χωρίστηκε σε δύο βακτήρια δεύτερης γενιάς, τα οποία χωρίστηκαν σε τέσσερα βακτήρια τρίτης γενιάς και ούτω καθεξής – μέχρι τα ~2K~ βακτήρια της γενιάς ~K+1~ που ανακάλυψαν οι επιστήμονες. Έχουν αριθμήσει τα βακτήρια χρησιμοποιώντας αριθμούς από το 1 έως το ~2^K~ με τον ακόλουθο τρόπο:

• Οι απόγονοι των βακτηρίων της προηγούμενης (~K~-οστής) γενιάς είναι, με αυτή τη σειρά: ~\{1,\;2\},\;\{3,\;4\},\;\{5,\;6\},\;\ldots\;,\;{2^K - 1,\;2^K}~
• Οι απόγονοι των βακτηρίων της παλαιότερης (~(K-1)~-οστής) γενιάς είναι, με αυτή τη σειρά: ~\{1,\;2,\;3,\;4\},\;\{5,\;6,\;7,\;8\},\;\ldots\;,\;\{2^K - 3,\;2^K - 2,\;2^K - 1,\;2^K\}~
• Οι απόγονοι βακτηρίων της ακόμη παλαιότερης (~(K-2)~-οστής) γενιάς είναι, με αυτή τη σειρά: ~\{1,\;2,\;3,\;4,\;5,\;6,\;7,\;8\},\;\ldots\;,\;\{2^K - 7,\;2^K - 6,\;2^K - 5,\;2^K - 4,\;2^K - 3,\;2^K - 2,\;2^K - 1,\;2^K\}~
• ~\ldots~
• Οι απόγονοι των δύο βακτηρίων της δεύτερης γενιάς είναι, με αυτή τη σειρά: ~\{1,\;2,\;\ldots\;,\;2^K-1\}~ και ~\{2^{K-1} + 1,\;2^{K-1} + 2,\;\ldots\;,\;2^K\}~

όπου τα άγκιστρα υποδηλώνουν ένα σύνολο απογόνων ενός μεμονωμένου βακτηρίου. Δηλαδή, τα ~2^K~ βακτήρια της τρέχουσας γενιάς αριθμήθηκαν έτσι ώστε οι απόγονοι οποιουδήποτε παλαιότερου βακτηρίου να έχουν διαδοχικούς αριθμούς.
Παρατηρήστε ότι υπάρχουν πολλές διαφορετικές μεταθέσεις αυτών των βακτηρίων που εξακολουθούν να ικανοποιούν τον κανόνα ότι οι απόγονοι οποιουδήποτε παλαιότερου βακτηρίου έχουν διαδοχικούς αριθμούς στη σειρά. Οι επιστήμονες θέλουν να τακτοποιήσουν τα βακτήρια σε μια τέτοια σειρά που έχει επίσης το ελάχιστο δυνατό μήκος. Το μήκος μιας ακολουθίας βακτηρίων είναι το άθροισμα των αποστάσεων μεταξύ όλων των γειτονικών ζευγών βακτηρίων.
Συγκεκριμένα, υπάρχει μια ορισμένη μετρήσιμη απώθηση μεταξύ κάθε δύο βακτηρίων, που είναι η ελάχιστη απόσταση μεταξύ τους εάν βρίσκονται το ένα δίπλα στο άλλο στην ακολουθία. (Η απώθηση δεν παίζει κανένα ρόλο μεταξύ βακτηρίων που δεν είναι άμεσοι γείτονες στην ακολουθία.) Δεδομένων των τιμών απώθησης για όλα τα ζεύγη βακτηρίων, βρείτε το ελάχιστο δυνατό μήκος μιας ακολουθίας βακτηρίων (μετάθεση) που να ικανοποιεί τον κανόνα απογόνων που δίνεται παραπάνω.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~K\;(1 \le K \le 9)~.
Κάθε μία από τις ακόλουθες ~2^K~ γραμμές περιέχει ~2^K~ ακέραιους αριθμούς από το διάστημα ~[0,\;10^6]~. Αυτοί οι ~2^K \times 2^K~ αριθμοί αντιπροσωπεύουν την απώθηση μεταξύ των ζευγών βακτηρίων: ο αριθμός στη σειρά ~m~ και στη στήλη ~n~ είναι η απώθηση μεταξύ των βακτηρίων ~m~ και ~n~. Αυτός ο αριθμός θα είναι, φυσικά, ίσος με τον αριθμό στη σειρά ~n~ και στη στήλη ~m~. Για ~m = n~ ο αριθμός θα είναι 0.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το ελάχιστο δυνατό μήκος μιας ακολουθίας βακτηρίων ικανοποιώντας τους περιορισμούς.

Παραδείγματα

input

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

output

13

input

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

output

32