def max_profit(prc_list, count):
    cache = {}
    return profit(prc_list, count, cache)


def profit(prc_list, cnt, cache):
    if cnt in cache:  # 계산 값이 있는지 체크
        return cache[cnt]
    if cnt == 1:  # 한 개만 파는 경우의 베이직 케이스
        cache[cnt] = prc_list[cnt - 1]
        return cache[cnt]
    if cnt == 0:  # 파는 개수 0개의 베이직 케이스
        return 0
    cache[cnt] = prc_list[cnt - 1]  # 사전 개수당 가격표 저장
    for i in range(cnt):  # 기본 가격표를 건들지 않는 선에서 개수 조합 별 수익 비교
        if cnt - i < i:
            break
        cache[cnt - i, i] = profit(prc_list, cnt - i, cache) + profit(prc_list, i, cache)
        if cache[cnt] < cache[cnt - i, i]:
            cache[cnt] = cache[cnt - i, i]
    return cache[cnt]


# test code
price_list = [100, 400, 800, 900, 1000]

print(max_profit(price_list, 5))