program atcoder
    implicit none
    integer(8) :: i,j,k,n
    integer(8),allocatable,dimension(:,:) :: dp
    integer(8),allocatable,dimension(:) :: a,sum
    read*,n
    allocate(dp(0:n,0:n))
    allocate(a(0:n))
    allocate(sum(0:n))

    ! dp(i,j) := i番目のスライムからj番目のスライムを合体させるための最小コスト
    dp = lshift( 1_8, 50 ) ! // 最小を求めたいので、初期値は大きい値にしておく
    sum = 0_8
    a = 0_8
    read(*,*)(a(i),i=1,n) ! スライムの大きさを受け取る
    do i=1,n
        sum(i) = sum(i-1) + a(i) ! 累積和を計算しておく -> 合体のコストを高速に計算するため
        dp(i,i) = 0_8 ! i==jではスライムが1体しかいないので合体コストは0,この情報からどのようにループをすればいいか考える
        ! 1体の次は2体の結合、次は3体の結合...と求められそう
        !    -> 考える区間が大きくなっていく
    enddo
    
    do i = 1,n ! i := 幅 -> 区間の幅が小さいものから決まっていくから
        do j = 1,n-i ! j := 左端 -> [j,j+i]の区間を考える
            do k = j,j+i-1 ! [j,k]と[k+1,j]の合体を考える , それぞれ今考えている区間の長さより短いので計算済みである
                dp(j,j+i) = min(dp(j,j+i) , dp(j,k)+dp(k+1,j+i)+sum(j+i)-sum(j-1))
                ! [i,j+i]のコストは[i,k],[k+1,j+i]にそれぞれかかったコストと今回かかるコストの和
                ! それぞれのkでminを取る
            enddo
        enddo
    enddo
    write(*,'(I0)')dp(1,n)

    stop 
contains
end program atcoder
