Combining Riceballs

Ο Αλφόνσο έχει ~N~ μπάλες ρυζιού διαφόρων μεγεθών σε μια σειρά. Θέλει να σχηματίσει τη μεγαλύτερη δυνατή μπάλα ρυζιού για να φάει ο φίλος του. Ο Αλφόνσο μπορεί να εκτελέσει τις ακόλουθες πράξεις:

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

Ο Αλφόνσο μπορεί να εκτελέσει κάθε πράξη όσες φορές θέλει.

Προσδιορίστε το μέγεθος της μεγαλύτερης μπάλας ρυζιού στη σειρά, μετά από την εκτέλεση ~0~ ή περισσότερων πράξεων.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον ακέραιο αριθμό ~N\;(1 \le N \le 400)~.

Η επόµενη γραµµή θα περιέχει ~N~ ακέραιους αριθµούς χωρισµένους με κενά διαστήματα, που θα αντιπροσωπεύουν τα µεγέθη από τις μπάλες ρυζιού, με τη σειρά, από αριστερά προς τα δεξιά. Κάθε ακέραιος θα είναι τουλάχιστον ~1~ και το πολύ ~1\;000\;000~.

• Για ~1~ από τους ~15~ διαθέσιμους βαθμούς, ~N = 4~.
• Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 10~.
• Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 50~.

Έξοδος

Εξάγετε το μέγεθος της μεγαλύτερης μπάλας ρυζιού που μπορεί να σχηματίσει ο Αλφόνσο.

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

input

7
47 12 12 3 9 9 3

output

48

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

Μια πιθανή σειρά κινήσεων για τη δημιουργία μιας μπάλας με μέγεθος ~48~ είναι να συνδυάσετε τις ~12~ και ~12~, σχηματίζοντας μια μπάλα μεγέθους ~24~. Στη συνέχεια, συνδυάστε τις ~9~ και ~9~ για να σχηματίσετε μια μπάλα με μέγεθος ~18~. Στη συνέχεια, συνδυάστε τις ~3~, ~18~ και ~3~ για να σχηματίσετε μια μπάλα ρυζιού μεγέθους ~24~. Τέλος, συνδυάστε τις δύο μπάλες μεγέθους ~24~ για να σχηματίσετε μια μπάλα μεγέθους ~48~.

input

4
1 2 3 1

output

3

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

Δεν υπάρχουν κινήσεις που να μπορούν να γίνουν, επομένως η μεγαλύτερη μπάλα στη σειρά είναι μεγέθους ~3~.