qkreltms

n = int(input())
p, d = [0] * (n+1), [0] * (n+1)
p = list(map(int, input().split()))
p.insert(0, 0)

for i in range(1, n+1):
    for j in range(1, i+1):
        if d[i] < d[i-j] + p[j]:
            d[i] = d[i-j] + p[j]
print(d[n])

qkreltms

def f(n):
    d = [0] * (n+1)
    d[0] = 1
    d[1] = 1
    for i in range(2, n+1):
        d[i] = d[i-1] + 2 * d[i-2]
        d[i] %= 10007
    return d[n]

qkreltms

def f(n, seq):
    print("Simulation %d" % ctn)
    cache = []
    for i in seq:
        for j in i:
            if j is "!":
                print(''.join(reversed(cache)))
                continue
            if j in cache:
                cache.pop(cache.index(j))

qkreltms

def f(str):
    while "()" in str:
        str = str.replace("()", "")
    if len(str) >= 1:
        print("NO")
    else:
        print("YES")


for _ in range(int(input())):

qkreltms

class Stack:
    def __init__(self, length):
        self.d = [None] * length
        self.top = -1

    def len(self):
        return self.top+1

    def append(self, item):
        self.top += 1

qkreltms

# 값은 잘 나오나, 시간초과가 발생한다. 알아보니 포함-배제의 원리를 사용한다고 한다. 일단 패스

def gcd(m: int, n: int):
    while n != 0:
        t = m % n
        m, n = n, t
    return abs(m)


def f(a: int, b: int, n: int):

qkreltms

# DP는 조합관련 문제에 사용, 조합 관련 문제일 때 점화식에 더하기 사용
# 타일 조합 문제의 경우 2x1을 제외하고 나머지는 2xn조합에서(n > 1)
# 주어진 타일을 조합하며 사용하면 되므로 더하기 사용
# 이 문제의 경우.
# 1일 때 (1), 2일 때 (1, 1), (2) 와 같은 조합처럼
# n=2 일때 n-3을 할 수 없음, 즉 n >= 0


def f(n):
    if n <= 1:

qkreltms

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class CircularLinkedList:
    def __init__(self):
        self.tail = None
        self.head = None

qkreltms

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.tail = None
        self.head = None

qkreltms

문제의 조건
2 x 1(세로) 타일과
1 x 2(가로) 타일을 사용해 
2 x n 타일을 채워라

1 x 2 를 사용시 1 x 2를 한 번더 사용해야하므로 2개를 1개로 취급 

타일의 크기가 n 일 때 세로 타일은 n칸에서 1칸을 차지 -> n-1 
  n-1    1
---------