26ος ΠΔΠ Καμπ (juniors)
Ανέβα τη σκάλα (stairstep)

Έστω μία σκάλα με \(N\) σκαλιά και δύο κεφαλόσκαλα, ένα στο κάτω μέρος και ένα στο πάνω. Σε κάθε σκαλί είναι γραμμένος ένας ακέραιος αριθμός. Στα δύο κεφαλόσκαλα είναι γραμμένος ο αριθμός μηδέν.

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

Ζητείται να βρείτε τη μέγιστη τιμή του αθροίσματος που μπορείτε να σχηματίσετε με αυτόν τον τρόπο.

Αρχεία Εισόδου (stairstep.in):

Η είσοδος θα αποτελείται από δύο γραμμές. Η πρώτη γραμμή θα περιέχει μόνο το φυσικό αριθμό \(N\): το πλήθος των σκαλιών. Η δεύτερη γραμμή θα περιέχει \(N\) ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα: οι αριθμοί αυτοί είναι γραμμένοι στα σκαλιά, κατά σειρά από κάτω προς τα πάνω. Η απόλυτη τιμή των αριθμών δε θα υπερβαίνει το \(1.000\).

Αρχεία Εξόδου (stairstep.out):

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

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

1^o

stairstep.in	stairstep.out
4 5 -3 -1 2	6

2^o

stairstep.in	stairstep.out
9 -21 -23 -69 -67 1 41 97 49 27	125

Εξήγηση παραδειγμάτων: Τα μέγιστα αθροίσματα επιτυγχάνονται όπως φαίνεται στα παρακάτω σχήματα.

Περιορισμοί

• \(1 \leq N \leq 1.000.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: 64 MB.