biblos

Din dorinţa de a realiza un fond de carte cât mai voluminos, oficialităţile oraşului Galaţi, au modernizat pentru început, o sală pentru depozitarea cărţilor şi l-au numit pe Biblos coordonatorul acestei biblioteci.

Achiziţionarea de carte s-a realizat în mai multe etape. De fiecare dată cărţile achiziţionate au fost depozitate pe câte un stativ construit special de Biblos. Pentru a avea spaţiu de depozitare Biblos a construit mai multe stative decât i-ar fi fost necesare, unele putând rămâne fără cărţi. După mai multe etape de achiziţionare, Biblos a constatat că spaţiul alocat bibliotecii este prea mic. Primind un alt spaţiu mai încăpător, mută primul stativ cu toate cărţile conţinute de acesta şi se opreşte deoarece îşi doreşte să mute acele stative care nu sunt aşezate unul lângă celălalt şi care fac ca fondul de carte din noua sală să fie cât mai mare posibil.

Cerință

Scrieţi un program care, cunoscând numărul stativelor, precum şi numărul de volume de carte de pe fiecare stativ, determină care este numărul maxim de volume care pot fi mutate în noua sală, ştiind că primul stativ a fost deja mutat iar celelalte se aleg astfel încât să nu fie aşezate unul lângă celălalt. Dacă există stative care nu au cărţi acestea nu vor fi mutate în a doua sală.

Date de intrare

Fişierul de intrare biblos.in conţine pe prima linie o valoare $n$, număr natural cu semnificaţia numărul de stative, pe a doua linie $n$ numere naturale, $x_1, x_2, \ldots, x_n$ separate prin câte un spaţiu cu semnificaţia $x_i =$ numărul de volume de carte existente pe fiecare stativ.

Date de ieșire

Fişierul de ieşire biblos.out va conţine o singură linie unde se află un număr natural cu semnificaţia: numărul maxim de volume ce au fost transferate.

Restricții și precizări

• $1 \leq n \leq 30 \ 000$
• $0 \leq x_i \leq 32 \ 767$, unde $i = 1 \ldots n$ iar $x_i$ reprezintă numărul de cărţi de pe stativul $i$
• Pentru $70\%$ dintre teste $n \leq 1 \ 000$
• Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie.

Exemplul 1

biblos.in

7
1 3 6 2 5 8 4

biblos.out

16

Explicație

Suma maximă se obţine din mutarea stativelor $1$(obligatoriu)$, 3, 5, 7$ (nu pot fi stative alăturate)

Exemplul 2

biblos.in

15
3 1 84 9 89 55 135 49 176 238 69 112 28 175 142

biblos.out

836

Explicație

Suma maximă obţinută din mutarea stativelor $1, 3, 5, 7, 10, 12, 14$

Exemplul 3

biblos.in

8
7 1 4 12 9 9 12 4

biblos.out

32

Explicație

Suma maximă obţinută din mutarea stativelor $1, 3, 5, 7$, sau din mutarea stativelor $1, 4, 6, 8$