N,*A = `dd`.split.map &:to_i
dp = (0...N).map{ Array.new(N, 0) }
sp = [0]
(0...N).each{ |x| sp << sp[-1] + A[x] }
(1...N).each{ |d|
  (0...N-d).each{ |x|
    y = x+d
    dpx = dp[x]
    dpy = dp[y]
    mc = dpx[x] + dpy[x+1]
    (x+2..y).each{ |k| c = dpx[k-1] + dpy[k]; mc = c if c < mc }
    dpy[x] = dpx[y] = mc + sp[y+1] - sp[x]
  }
}
p dp[0][-1]
