Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

gold

There are N magical boxes along a road, each of which has a certain amount of gold: in the k-th box there is exactly gk kilogram gold (k=1...N). If we get the gold from a box then the neighbouring boxes slide away. The boxes are in far away from each other, so we cannot get the gold from two or more boxes at the same time. What is the maximal amount of gold (M) that we can get?

Example

N: 5
gold in the boxes: 3 7 5 4 2
by exploring all possible ways, one can see that M=11:

    box id          gold
    1,3,5          3+5+2
     1,4             3+4
     2,4             7+4 -> max 
     2,5             7+2

Input Specification


N
g1 ... gN

The first line with the number 1 ≤ N ≤ 104 and the second line with the comma separated numbers 1 ≤ gk ≤ 104 (k=1...N).

Output Specification

M

A single line with the required M.

Sample Input 1

  1. 5
  2. 3 7 5 4 2
download as text file

Sample Output 1

  1. 11
download as text file

Sample Input 2

  1. 7
  2. 1 2 3 3 2 2 1
download as text file

Sample Output 2

  1. 7
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019