/*
TASK:bus
LANG:C++
*/

#include <cstdio>
//#include <conio.h>
#include <algorithm>
using namespace std;

#define MN      1024
#define INF     1000000010

int A[MN];
int N,K;

int f[MN][MN];
int g[MN][MN];
int dp_sum[MN];


inline int getSum(int i,int j)
{
    return dp_sum[j]-dp_sum[i-1];
/*    int r=0;
    for (int k=i;k<=j;++k) r+=A[k];
    return r;*/
}

int main()
{
    //freopen("a2.in","r",stdin);
    
    scanf("%d%d",&N,&K);
    if (K>N) K=N;
    for (int i=1;i<=N;++i) scanf("%d",&A[i]);
    
    // prep
    dp_sum[0]=0;
    for (int i=1;i<=N;++i) dp_sum[i]=dp_sum[i-1] + A[i];
    
    int i,j,k;
    int acc,bpos,cpos,cv1,cv2,bv1,bv2;
    
    
    for (i=1; i<N; ++i) {
        if (i==1) {
            acc=0;
            for (j=i;j<N;++j) {
                acc += A[j]*abs(j-i);
                f[i][j]=acc;
            }
            continue;
        }
        
        for (j=i; j<N; ++j) {

            cpos=i,cv1=0,cv2=0;
            for (k=i+1;k<=j;++k) cv2+=A[k]*abs(k-i);
            
            bpos=i;
            bv1=cv1; bv2=cv2;
            
            for (cpos=i+1; cpos<=j; ++cpos) {
                cv1+=getSum(i,cpos-1);
                cv2-=getSum(cpos,j);
                
                if (cv1+cv2 < bv1+bv2) {
                    bv1=cv1; bv2=cv2;
                    bpos=cpos;
                }
            }
            
            //printf("%d %d: %d bv1=%d bv2=%d\n",i,j,bpos, bv1,bv2);
            f[i][j]=bv1+bv2;
        }
    }
    
    acc=0;
    j=N;
    for (i=N; i>=1; --i) {
        acc += A[i]*abs(j-i);
        f[i][j] = acc;
    }

    f[1][N]=INF;
    
    
    memset(g[1],0,sizeof(g[1]));
    int mnK_i;
    
    for (i=2;i<=N;++i) {
        if (i==N) g[N][1]=INF;
        else g[i][1] = f[1][i];
        
        mnK_i=min(K,i); // opt.
        
        for (k=2; k<=mnK_i; ++k) {
            g[i][k]=INF;
            
            for (j=i; j>1; --j) {
                if (g[i][k] > g[j-1][k-1] + f[j][i])
                    g[i][k] = g[j-1][k-1] + f[j][i];
            }
            
            //printf("%d %d: %d\n",i,k,g[i][k]);
        }
    }
    
    int ans=INF;
    for (k=2;k<=K;++k) ans=min(ans, g[N][k]);
    printf("%d\n",ans);
    
    //getch();
    return 0;
}
