/*
TASK: bus
LANG: C
*/
#include <stdio.h>
#define MAXN 1024
#define INF (int)1e9

 int down[MAXN];
 int up[MAXN];
 int a[MAXN];
 int n,m;
 int opt[MAXN][MAXN];
 int b[MAXN][MAXN];
 int dt[MAXN];
 int ut[MAXN];

 int min (int a,int b) {  return a<b?a:b; }

 int calcd (int i,int j)
  {
   return down[i+1]-dt[j+1]*(j-i)-down[j+1];
  }

 int calcu (int i,int j)
  {
   return up[j-1]-ut[i-1]*(j-i)-up[i-1];
  }

 void update (int k,int i,int j)
  {
   int med,pom;
   med=(k+i)/2;
   pom=b[k][j-1]+calcd(k,med)+calcu(med+1,i);
   if (b[i][j]>pom)
    {
     b[i][j]=pom;
     opt[i][j]=k;
    }
  }

 int main ()
  {
   int i,j,k;
   scanf("%d%d",&n,&m);
   m=min(m,n);
   for (i=1;i<=n;i++)
    scanf("%d",&a[i]);
   for (i=1;i<=n;i++)
    {
     ut[i]=a[i]+ut[i-1];
     up[i]=up[i-1]+ut[i];
    }
   for (i=n;i>=1;i--)
    {
     dt[i]=a[i]+dt[i+1];
     down[i]=down[i+1]+dt[i];
    }
   for (i=0;i<=n+1;i++)
    for (j=0;j<=m+1;j++)
     b[i][j]=INF;
   b[1][1]=0;
   opt[1][1]=1;
   for (i=2;i<=n;i++)
    {
     update(1,i,2);
     for (j=3;j<=min(m,i);j++)
       for (k=opt[i][j-1];k<i;k++)
        update(k,i,j);
    }
   printf("%d\n",b[n][m]);
   return 0;
  }
  
