Putnik

Οι πιθανότητες είναι ότι έχετε μάλλον ήδη ακούσει για το πρόβλημα του ταξιδιώτη πωλητή. Εάν έχετε, τότε γνωρίζετε ότι είναι ένα NP-σκληρό πρόβλημα επειδή δεν διαθέτει αποτελεσματική λύση. Λοιπόν, αυτή η εργασία είναι μια ασυνήθιστη εκδοχή του διάσημου προβλήματος! Το ασυνήθιστο του πηγάζει από το γεγονός ότι αυτή η εκδοχή είναι, στην πραγματικότητα, επιλύσιμη.

Ο ταξιδιώτης πωλητής είναι σε αποστολή να επισκεφτεί \(Ν\) πόλεις, η καθεμία ακριβώς μία φορά. Οι πόλεις αντιπροσωπεύονται από τους αριθμούς ~1,\;2,\;\ldots\;,\;N~. Αυτό που γνωρίζουμε είναι η διάρκεια απευθείας πτήσης μεταξύ κάθε ζεύγους πόλεων. Ο πωλητής, όντας ο αποτελεσματικός άνθρωπος που είναι, θέλει να τροποποιήσει τη σειρά επισκέψεων στην πόλη έτσι ώστε η συνολική διάρκεια πτήσης να είναι η ελάχιστη δυνατή.

Δυστυχώς, όλα δεν είναι τόσο απλά. Επιπλέον, ο πωλητής έχει μια ιδιόμορφη συνθήκη σχετικά με τη σειρά. Για κάθε πόλη με την ένδειξη ~K~ πρέπει να ισχύει: είτε όλες οι πόλεις με ετικέτες μικρότερες από ~K~ έχουν επισκεφτεί πριν από την πόλη με την ένδειξη ~K~ ή όλες θα επισκέψουν μετά την πόλη με την ένδειξη ~K~. Με άλλα λόγια, η κατάσταση όταν μια από αυτές τις πόλεις έχει επισκεφθεί πριν, και η άλλη μετά δεν επιτρέπεται.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(2 \leq N \leq 1500)~, τον αριθμό των πόλεων.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ~N~ θετικούς ακέραιους από το διάστημα ~[0,\;1000]~. Ο αριθμός στη ~B~-οστή θέση στην ~A~-οστή σειρά αντιπροσωπεύει τη διάρκεια πτήσης μεταξύ των πόλεων ~A~ και ~B~, ο αριθμός αυτός είναι ίσος με τον ~A~-οστό αριθμό στη ~B~-οστή σειρά. Όταν ~A = B~, αυτός ο αριθμός είναι 0. Διαφορετικά, είναι θετική τιμή.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~1/3~ των συνολικών πόντων, το ~N~ θα είναι το πολύ ~10~.

Σε περιπτώσεις δοκιμής αξίας ~1/2~ των συνολικών πόντων, το ~N~ θα είναι το πολύ ~20~.

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

input

3
0 5 2
5 0 4
2 4 0

output

7

Επεξήγηση του 1ου παραδείγματος:

Η βέλτιστη ακολουθία είναι ~2,\;1,\;3~ ή ~3,\;1,\;2~. Η ακολουθία ~1,\;3,\;2~ είναι ακόμη πιο ευνοϊκή, αλλά δεν πληροί τις προϋποθέσεις του πωλητή.

input

4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0

output

31

Επεξήγηση του 2ου παραδείγματος:

H ακολουθία είναι είτε ~3,\;1,\;2,\;4~ είτε ~4,\;2,\;1,\;3~.