Spijuni

Είστε ο Μ, ο επικεφαλής της υπηρεσίας πληροφοριών που απασχολεί ~N~ κατασκόπους με κωδικές ονομασίες από το ~1~ έως το ~N~. Σε καθέναν από τους κατασκόπους έχει ανατεθεί μια διαφορετική χώρα και έλαβε μια σημαντική πληροφορία εκεί. Το καθήκον σας είναι το εξής:

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

Το να στείλεις ένα κατάσκοπο ~k~ στην αποστολή κοστίζει ~M_k~. Για να πετύχει η αποστολή, είναι σημαντικό οι κατάσκοποι μαζί να γνωρίζουν όλες τις πληροφορίες που αποκτήθηκαν από τους υπόλοιπους κατασκόπους.

Βρείτε την ελάχιστη συνολική τιμή προετοιμασίας και εκτέλεσης αυτής της αποστολής.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~N~, τον αριθμό των κατασκόπων ~(2 \le N \le 1\,000)~.
Καθεμία από τις ακόλουθες ~N~ γραμμές περιέχει ~N~ θετικούς ακέραιους που δεν υπερβαίνουν το ~10^6~. Ο αριθμός στη σειρά ~k~ και στη στήλη ~m~ αντιπροσωπεύει την τιμή μιας συνάντησης μεταξύ των κατασκόπων ~k~ και ~m~ και, φυσικά, ισούται με τον αριθμός στη σειρά ~m~ και στη στήλη ~k~ (για ~k = m~ ο αριθμός θα είναι ~0~).
Η ακόλουθη γραμμή περιέχει ~N~ θετικούς ακέραιους ~M_k (1 \le M_k \le 10^6)~, τις τιμές αποστολής κάθε κατασκόπου σε μια αποστολή, με τη σειρά για τους κατασκόπους ~1, 2, \ldots, N~.

Έξοδος

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

Βαθμολογία

Σε δεδομένα δοκιμής με ~N \le 30~, που αξίζουν συνολικά ~40~ βαθμούς, θα είναι βέλτιστο να στείλετε το πολύ τέσσερις κατασκόπους στην αποστολή.
Σε δεδομένα δοκιμών συνολικής αξίας ~50~ πόντων, όλες οι τιμές αποστολής κατασκόπων σε αποστολή είναι ίσες.

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

input

3
0 6 9
6 0 4
9 4 0
7 7 7

output

17

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

Θα οργανώσουμε συναντήσεις μεταξύ των κατασκόπων ~1~ και ~2~, μετά ~2~ και ~3~, και θα στείλετε τον κατάσκοπο ~2~ για την αποστολή.

input

3
0 17 20
17 0 10
20 10 0
15 9 12

output

34

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

Θα οργανώσουμε μια συνάντηση μεταξύ των κατασκόπων ~2~ και ~3~ και θα στείλουμε τους κατασκόπους ~1~ και ~2~ στην αποστολή.

input

5
0 3 12 15 11
3 0 14 3 20
12 14 0 11 7
15 3 11 0 15
11 20 7 15 0
5 10 10 10 10

output

28

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

Θα οργανώσουμε συναντήσεις μεταξύ των κατασκόπων ~2~ και ~4~, μετά ~1~ και ~2~, μετά ~3~ και ~5~ και θα στείλουμε τους κατασκόπους ~1~ και ~3~ (ή ~1~ και ~5~) στην αποστολή.