Pripreme

Ο Ante και ο Goran προετοιμάζουν ~N~ ομάδες νέων φιλόδοξων φοιτητών για έναν φοιτητικό διαγωνισμό προγραμματισμού φοιτητών από το Πανεπιστήμιο του Zagreb. Και οι δύο έχουν έναν αλγόριθμο που πρέπει να εξηγήσουν σε κάθε ομάδα. Φυσικά, και οι δύο δεν μπορούν να εργαστούν με την ίδια ομάδα ταυτόχρονα και καμία από αυτές δεν μπορεί να συνεργαστεί με πολλές ομάδες ταυτόχρονα.

Σας δίνεται ο χρόνος που χρειάζεται για κάθε ομάδα να κατανοήσει και να εφαρμόσει έναν αλγόριθμο. Κάθε διάλεξη αλγορίθμου πρέπει να γίνεται χωρίς διακοπή. Προσδιορίστε τον ελάχιστο χρόνο που απαιτείται για τον Άντε και τον Γκόραν για να κάνουν τις διαλέξεις τους!

Για πρόσθετη εξήγηση, συμβουλευτείτε τις διευκρινίσεις των παραδειγμάτων.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N~, τον αριθμό των ομάδων.
Η ακόλουθη γραμμή περιέχει ~N~ ακέραιους αριθμούς χωρισμένους με διάστημα, όπου ο ~i~-οστός ακέραιος υποδηλώνει το χρόνο που απαιτείται για την ~i~-οστή ομάδα να κατανοήσει και να εφαρμόσει έναν αλγόριθμο.
Όλοι οι αριθμοί στην είσοδο θα ανήκουν στο διάστημα ~[1,\;3 \times 10^5]~.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας ~40~% των συνολικών πόντων, θα κατέχει το ~N \leq 7~.

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

input

3
2 2 2

output

6

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

Κάθε ομάδα χρειάζεται 2 μονάδες χρόνου για να κατανοήσει και να εφαρμόσει έναν αλγόριθμο. Ένα από τα πιθανά προγράμματα είναι ότι ο Ante δίνει τις διαλέξεις του στην ομάδα 1, ομάδα 2 και ομάδα 3, αντίστοιχα, και ο Goran στην ομάδα 3, ομάδα 1 και ομάδα 2, αντίστοιχα.

input

3
4 1 2

output

8

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

Ένα από τα βέλτιστα προγράμματα είναι ότι ο Ante δίνει διαλέξεις στην ομάδα 2, ομάδα 3 και ομάδα 1, αντίστοιχα, αλλά με μια παύση που διαρκεί 1 μονάδα χρόνου μεταξύ της ομάδας 3 και της ομάδας 1. Ο Goran θα δώσει διαλέξεις στην ομάδα 1, ομάδα 3 και ομάδα 2, αντίστοιχα.

input

4
1 3 2 1

output

7