def MEMOIZEDCUTROD(p, n):
    r=[]
    for i in range ( 0 , n ):

        r.append(0)

        r[i] = float('-inf')

    return MEMOIZEDCUTRODAUX(p, n, r)

def MEMOIZEDCUTRODAUX(p, n, r):

    if r[n] >= 0:

        return r[n]

    elif n == 0:

        q = 0

    else:

        q = float('-inf')

        for i in range(1,n):

            q = max(q, p[i] + MEMOIZEDCUTRODAUX(p, n-i, r))
    r[n] = q
    return q

p=[1,5,8,9,10,17,17,20,24,30]
n=len(p)
print(MEMOIZEDCUTROD(p, n))