CodeEff/ECCO huggingface dataset:
# Original solution
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def cost(l, r):
        if l + 2 == r:
            return aa[l] + aa[l + 1]
        if l + 1 == r:
            return 0
        if dp[l][r] != -1:
            return dp[l][r]
        res = 10 ** 10
        for m in range(l + 1, r):
            res = min(res, cost(l, m) + cost(m, r))
        res += cumsum_aa[r] - cumsum_aa[l]
        dp[l][r] = res
        return res

    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    cumsum_aa = [0]
    for i, a in enumerate(aa):
        cumsum_aa.append(cumsum_aa[i] + a)
    print(cost(0, n))

main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def cost(l, r):
        if l + 2 == r:
            return aa[l] + aa[l + 1]
        if l + 1 == r:
            return 0
        if dp[l][r] != -1:
            return dp[l][r]
        res = 10 ** 16
        for m in range(l + 1, r):
            res = min(res, cost(l, m) + cost(m, r))
        res += cumsum_aa[r] - cumsum_aa[l]
        dp[l][r] = res
        return res

    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    cumsum_aa = [0]
    for i, a in enumerate(aa):
        cumsum_aa.append(cumsum_aa[i] + a)
    print(cost(0, n))

main()
# Original solution
from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(eval(input()))
A = list(map(int, input().split()))

dp = [[float('inf')]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


dfs(0, N)
print((dp[0][-1]))


# Optimized solution
from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(eval(input()))
A = list(map(int, input().split()))

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
ans = int(dp[0][-1])
print(ans)
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(eval(input()))
    A = list(map(int, input().split()))
    S = [0] * (n + 1)
    for i in range(n):
        S[i + 1] = S[i] + A[i]

    @lru_cache(None)
    def dfs(l, r):
        # base case
        if r - l == 1:
            return 0
        # recursion
        return min(dfs(l, m) + dfs(m, r) + S[r] - S[l] for m in range(l + 1, r))

    print((dfs(0, n)))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(eval(input()))
    A = list(map(int, input().split()))
    S = [0] * (n + 1)
    for i in range(n):
        S[i + 1] = S[i] + A[i]

    dp = [[None] * (n + 1) for _ in range(n + 1)]
    for l in range(n):
        dp[l][l + 1] = 0

    for width in range(2, n + 1):
        for l in range(n - width + 1):
            r = l + width
            res = INF
            for m in range(l + 1, r):
                res = min(res, dp[l][m] + dp[m][r] + S[r] - S[l])
            dp[l][r] = res

    print((dp[0][n]))
resolve()
# Original solution
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
acc = [0] + list(accumulate(A))
dp = [[0] * n for _ in range(n)]

def f(l, r):
    if dp[l][r]:
        return dp[l][r]
    if l == r:
        return 0
    m = INF
    for i in range(l, r):
        m = min(m, f(l, i) + f(i + 1, r) + acc[r + 1] - acc[l])
    dp[l][r] = m
    return m

print((f(0, n-1)))




# Optimized solution
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
acc = [0] + list(accumulate(A))
dp = [[0] * n for _ in range(n)]

def f(l, r):
    if dp[l][r] or l == r:
        return dp[l][r]
    m = INF
    for i in range(l, r):
        m = min(m, f(l, i) + f(i + 1, r) + acc[r + 1] - acc[l])
    dp[l][r] = m
    return m

print((f(0, n-1)))
# Original solution
inf = float('inf')

n = int(eval(input()))
a = tuple(int(x) for x in input().split())

d = [[inf] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0

c = [0]
for aa in a:
    c.append(c[-1] + aa)

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            # [i, k], (k, j]
            d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j])
        d[i][j] += c[j + 1] - c[i]
# print(d)
# print(c)
print((d[0][n - 1]))


# Optimized solution
inf = 10 ** 16

n = int(eval(input()))
a = tuple(int(x) for x in input().split())

d = [[inf] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0

c = [0]
for aa in a:
    c.append(c[-1] + aa)

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j):
            # [i, k], (k, j]
            d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j])
        d[i][j] += c[j + 1] - c[i]
# print(d)
# print(c)
print((d[0][n - 1]))
# Original solution
def solve(n, a):
    from itertools import accumulate

    inf = (400 ** 2) * (10 ** 9) + 10

    # [l,r)
    def dfs(l, r):
        if memo[l][r] != -1:
            return memo[l][r]
        if r - l == 1:
            return 0
        res = inf
        for c in range(l + 1, r):
            # [l, c), [c, r)
            res = min(res, dfs(l, c) + dfs(c, r))
        res += acc[r] - acc[l]
        memo[l][r] = res
        return res

    acc = (0,) + tuple(accumulate(a))
    memo = [[-1] * (n + 1) for _ in range(n + 1)]

    return dfs(0, n)


if __name__ == '__main__':
    n = int(eval(input()))
    a = tuple(map(int, input().split()))
    print((solve(n, a)))


# Optimized solution
def solve(n, a):
    from itertools import accumulate

    inf = (400 ** 2) * (10 ** 9) + 10

    acc = (0,) + tuple(accumulate(a))
    cost = [[inf] * (n + 1) for _ in range(n + 1)]
    for i in range(n):
        cost[i][i + 1] = 0

    for l in range(n - 1, -1, -1):
        for r in range(l + 2, n + 1):
            for c in range(l + 1, r):
                cost[l][r] = min(cost[l][r], cost[l][c] + cost[c][r])
            cost[l][r] += acc[r] - acc[l]

    return cost[0][n]


if __name__ == '__main__':
    n = int(eval(input()))
    a = tuple(map(int, input().split()))
    print((solve(n, a)))
# Original solution
N = int(eval(input()))
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict, deque

dp = defaultdict(lambda: -1)

q = deque([])
q.append((A, 0))

inf = float("inf")

ans = inf
while q:
    t, cost = q.popleft()
    if len(t) == 0:
        ans = min(ans, cost)
        continue

    if len(t) == 1:
        ans = min(ans, cost + t[0])
        continue

    tpl = t
    for i in range(len(tpl) - 1):
        if not (tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], tpl[i] + tpl[i + 1]) in q:
            q.append((tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], cost + tpl[i] + tpl[i + 1]))

print((ans - sum(A)))
exit(0)



# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
inf = float("inf")

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print((dfs(0,N)- sum(A)))
# Original solution
from itertools import accumulate

N, *A = list(map(int, open(0).read().split()))

S = [0] + list(accumulate(A))

memo = {}
def dp(L, R):
    if L == R:
        return 0
    if (L, R) in memo:
        return memo[(L, R)]

    memo[(L, R)] = min(dp(L, c) + dp(c + 1, R) + S[R + 1] - S[L] for c in range(L, R))
    return memo[(L, R)]

print((dp(0, N - 1)))

# Optimized solution
from itertools import accumulate

N, *A = list(map(int, open(0).read().split()))

S = [0] + list(accumulate(A))

memo = [[-1] * N for _ in range(N)]
def dp(L, R):
    if L == R:
        return 0
    if memo[L][R] >= 0:
        return memo[L][R]

    memo[L][R] = min(dp(L, c) + dp(c + 1, R) + S[R + 1] - S[L] for c in range(L, R))
    return memo[L][R]

print((dp(0, N - 1)))
# Original solution
import sys,queue,math,copy,itertools,bisect,collections,heapq
INF = 10**18
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = LI()
sn = [[0 for _ in range(N)] for _ in range(N)]
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    x = 0
    for j in range(i,N):
        x += a[j]
        sn[i][j] = x
for i in range(N):
    dp[i][i] = 0
    if i < N-1:
        dp[i][i+1] = sn[i][i+1]

for j in range(2,N):
    for i in range(j-2,-1,-1):
        for k in range(0,j-i):
            dp[i][j] = min(dp[i][j],dp[i+k+1][j]+ dp[i][i+k] + sn[i][j])
print((dp[0][-1]))


# Optimized solution
import sys
INF = 10**14
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = LI()
sn = [[0 for _ in range(N)] for _ in range(N)]
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    x = 0
    for j in range(i,N):
        x += a[j]
        sn[i][j] = x
for i in range(N):
    dp[i][i] = 0

for j in range(1,N):
    for i in range(j-1,-1,-1):
        for k in range(0,j-i):
            dp[i][j] = min(dp[i][j],dp[i+k+1][j]+ dp[i][i+k] + sn[i][j])
print((dp[0][-1]))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

#dp[l][r] = [l, r)区間のスライムを
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    else:
        res = float("inf")
        if (r - l) == 1:
            dp[l][r] = 0
            return dp[l][r]
        for k in range(l, r):
            if k == l or k == r:
                continue
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print((dp[0][n]))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[-1]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print((dp[0][n]))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print((dp[0][n]))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r, infnum):
    if dp[l][r] != infnum:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n, float("inf"))
print((dp[0][n]))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r, infnum):
    if dp[l][r] != infnum:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n, float("inf"))
print((dp[0][n]))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
ruiseki = [0] * (n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]

dp = [[-1]*(n+1) for i in range(n+1)]

def solve(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = 0
        return dp[l][r]
    ans = 10**18
    for i in range(l+1, r):
        ans = min(ans, solve(l, i) + solve(i, r) + ruiseki[r] - ruiseki[l])
    dp[l][r] = ans
    return dp[l][r]

solve(0, n)
print((dp[0][n]))
# Original solution
def main():
    N = int(eval(input()))
    a = list(map(int, input().split()))

    dp = [[10**13]*N for i in range(N)]
    s = [0] * (N+1)
    for i, x in enumerate(a):
        s[i+1] = s[i] + x
        dp[i][i] = 0
    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            tmp = s[j+1] - s[i]
            D = dp[i]
            for k in range(i, j):
                if D[j] > D[k]+dp[k+1][j] + tmp:
                    D[j] = D[k]+dp[k+1][j] + tmp

    print((dp[0][N-1]))
main()


# Optimized solution
def main():
    N = int(eval(input()))
    a = list(map(int, input().split()))

    dp = [[10**13]*N for i in range(N)]
    s = [0] * (N+1)
    for i in range(N):
        s[i+1] = s[i] + a[i]
        dp[i][i] = 0
    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            tmp = s[j+1] - s[i]
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j] + tmp)

    print((dp[0][N-1]))


main()
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    N = int(eval(input()))
    a = list(map(int, input().split()))
    inf = 10 ** 13
    dp = [[0]*N for i in range(N)]
    s = [0] * (N+1)
    for i, x in enumerate(a):
        s[i+1] = s[i] + x
        dp[i][i] = 0
    for i in range(N-2, -1, -1):
        DP = dp[i]
        si = s[i]
        for j in range(i+1, N):
            tmp = s[j+1] - si
            D = inf
            for k in range(i, j):
                if D > DP[k]+dp[k+1][j]:
                    D = DP[k]+dp[k+1][j]
            DP[j] = D + tmp
    print((dp[0][N-1]))


main()


# Optimized solution
def main():
    import sys
    from itertools import accumulate
    input = sys.stdin.readline
    N = int(eval(input()))
    a = list(map(int, input().split()))
    inf = 10 ** 13
    dp = [[0]*N for i in range(N)]
    s = [0] + list(accumulate(a))
    for i, x in enumerate(a):
        dp[i][i] = 0
    for i in range(N-2, -1, -1):
        DP = dp[i]
        si = s[i]
        for j in range(i+1, N):
            tmp = s[j+1] - si
            D = inf
            for k in range(i, j):
                cost = DP[k]+dp[k+1][j]
                if D > cost:
                    D = cost
            DP[j] = D + tmp
    print((dp[0][N-1]))


main()
# Original solution
def calc(A,n,dp):
    if n==2:
        return A[0]+A[1]
    s=10**18
    for i in range(0,n-1):
        B=[]
        B=A[0:i]
        B.append(A[i]+A[i+1])
        B=B+A[i+2:]
        l=str(B)
        if l in dp:
            s=min(s,A[i]+A[i+1]+dp[l])
        else:
            d=calc(B,n-1,dp)
            s=min(s,A[i]+A[i+1]+d)
            dp[l]=d

    return s
n=int(eval(input()))
A=list(int(i) for i in input().split())
dp={}
print((calc(A,n,dp)))
#for i in range(n):


# Optimized solution
n=int(eval(input()))
A=list(int(i) for i in input().split())
prefixsum=[0 for i in range(n+1)]
for i in range(1,n+1):
    prefixsum[i]=A[i-1]+prefixsum[i-1]
#print(prefixsum)
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(i,n):
        #starting index i and ending j
        #finally we need to print first row last column
        #which represent the cost of all the elements
        if i==j:
            dp[i][j]=0
        else:
            dp[i][j]=10**18
            for k in range(i,j):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+prefixsum[j+1]-prefixsum[i])
print((dp[0][-1]))
# Original solution
N = int(eval(input()))
A = [int(a) for a in input().split()]

dp = [[0] * N for _ in range(N)]

for d in range(1, N):
    for l in range(N-d):
        r = l + d
        if d == 0:
            dp[l][r] = A[l]
            
        else:
            dp[l][r] = 10**20
            for m in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + sum(A[l:r+1]))
    

print((dp[0][N-1]))

# Optimized solution
N = int(eval(input()))
A = [int(a) for a in input().split()]
B = [0]
for a in A:
    B.append(B[-1]+a)

dp = [[0] * N for _ in range(N)]

for d in range(1, N):
    for l in range(N-d):
        r = l + d
        if d == 0:
            dp[l][r] = A[l]
            
        else:
            dp[l][r] = 10**20
            for m in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + B[r+1]-B[l])
    
print((dp[0][N-1]))
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

def dp(i,j):
    if i >= j:
        return 0
    if (i,j) not in memo:
        ans = float("inf")
        for k in range(i,j):
            temp = dp(i,k) + dp(k+1,j) + p[j+1] - p[i]
            ans = min(ans,temp)
        memo[i,j] = ans
    return memo[i,j]
print((dp(0,n-1)))

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

dp = [[0 for _ in range(n)] for _ in range(n)]
for l in range(2,n+1):
    for i in range(n-l+1):
        dp[i][i+l-1] = min([dp[i][k] + dp[k+1][i+l-1] for k in range(i,i+l-1)]) + p[i+l] - p[i]
print((dp[0][n-1]))
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
memo = {}
p = [0]
for num in a:
    p += [p[-1] + num]

dp = [[0 for _ in range(n)] for _ in range(n)]
for l in range(2,n+1):
    for i in range(n-l+1):
        dp[i][i+l-1] = min([dp[i][k] + dp[k+1][i+l-1] for k in range(i,i+l-1)]) + p[i+l] - p[i]
print((dp[0][n-1]))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
dp = [[0] * (n+1) for _ in range(n+1)]
s = [0] * (n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        dp[i][j] = s[j] - s[i] + min(dp[i][k] + dp[k][j] for k in range(i+1, j))
print((dp[0][n]))
# Original solution
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N = int(eval(input()))
A = list(map(int,input().split()))

dp = [[0]*(N+1) for i in range(N+1)]

flag = [[0]*(N+1) for i in range(N+1)]

cA = [0]*(N+1)
for i in range(1,N+1) :
    cA[i] = cA[i-1] + A[i-1]

def f(left, right) :
    if flag[left][right] :
        return dp[left][right]
    elif left == right :
        return 0
    else :
        res = float("inf")
        for i in range(left, right) :
            res = min(res, f(left, i) + f(i+1, right))
        res += cA[right+1] - cA[left]
        dp[left][right] = res
        return res

ans = f(0,N-1)

print(ans)

#print(cA)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))

dp = [[10**18]*N for i in range(N)]

cA = [0]*(N+1)
for i in range(1,N+1) :
    cA[i] = cA[i-1] + A[i-1]

    dp[i-1][i-1] = 0

for d in range(1,N) :
    for i in range(N-d) :
        for cut in range(i, i+d) :
            dp[i][i+d] = min(dp[i][i+d], dp[i][cut] + dp[cut+1][i+d] + cA[i+d+1] - cA[i])

ans = dp[0][N-1]

print(ans)