Funghi

Αφού έφαγαν όλα τα μπισκότα από το σπίτι της κακιάς μάγισσας, ο Hansel και η Gretel παρήγγειλαν μια τζάμπο πίτσα. Η πίτσα έφτασε σε λίγο, κομμένη σε οκτώ κομμάτια. Ο Hansel και η Gretel πρόκειται να χωρίσουν την πίτσα στη μέση, ώστε ο καθένας τους να πάρει έναν πλήρη "μισό κύκλο" πίτσας ή, με άλλα λόγια, τέσσερα συνεχόμενα κομμάτια.

Στην Gretel αρέσουν πολύ τα μανιτάρια και θέλει να πάρει όσα περισσότερα μπορεί. Δεδομένου του γεγονότος ότι μερικές φέτες πίτσας περιέχουν λιγότερα και μερικές περισσότερα μανιτάρια, η Gretel ζήτησε από τον Hansel να χωρίσει την πίτσα έτσι ώστε τα κομμάτια της να περιέχουν όσο το δυνατόν περισσότερα μανιτάρια.

Βοηθήστε τον Hansel και την Gretel! Θα σας πουν πόσα μανιτάρια υπάρχουν σε καθεμία από τις οκτώ φέτες πίτσας και η δουλειά σας είναι να βρείτε τον μεγαλύτερο συνολικό αριθμό μανιταριών που μπορεί να πάρει η Gretel. Η ακόλουθη εικόνα απεικονίζει τη βέλτιστη διαίρεση για το δεύτερο δείγμα δοκιμής παρακάτω (1. υποδηλώνει την πρώτη τομή που δίνεται στα δεδομένα εισόδου):

Είσοδος

Κάθε μία από τις οκτώ γραμμές εισόδου περιέχει τον ακέραιο ~S_i(0 \leq S_i \leq 50,\;i = 1,\;2,\;\ldots,\;8)~. Αυτοί οι αριθμοί είναι, αντίστοιχα, η ποσότητα των μανιταριών στις φέτες πίτσας, όπου οι φέτες δίνονται με τη φορά των δεικτών του ρολογιού.

Έξοδος

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

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

input

5
2
1
4
5
1
2
3

output

12

input

2
6
5
3
3
7
2
6

output

19