/*
TASK:bus
LANG:C++
*/
#include<stdio.h>
//#define min(a,b) (a<b?a:b)
#define MAX 1010

int n,k,masiv[MAX],x,y,left[MAX],right[MAX],a;
int money1[MAX][MAX],money2[MAX][MAX],money[MAX][MAX],dp[MAX][MAX];
int p2[20];
//int masiv[MAX][MAX];


void z(int start,int lef);

void pre()
{
scanf("%d%d",&n,&k);
p2[0]=1;
for(x=1;x<=20;x++)p2[x]=p2[x-1]*2;
for(x=1;x<=n;x++)
                 scanf("%d",&masiv[x]);
left[1]=masiv[1];
for(x=2;x<=n;x++)
                 left[x]=left[x-1]+masiv[x];

right[n]=masiv[n];
for(x=n-1;x>0;x--)
                  right[x]=right[x+1]+masiv[x];

for(a=1;a<=n;a++)
{
money1[a][a]=0;
for(x=a+1;x<=n;x++)
money1[a][x]=money1[a][x-1]+masiv[x]*(x-a);
}

for(a=n;a>=1;a--)
{
money2[a][a]=0;
for(x=a-1;x>=1;x--)
money2[x][a]=money2[x+1][a]+masiv[x]*(a-x);
}

for(x=1;x<=n;x++)
{
for(a=0;x+a*2+1<=n;a++)
                       money[x][x+a*2+1]=money1[x][x+a]+money2[x+a+1][x+a*2+1];
for(a=0;x+a*2<=n;a++)
                     money[x][x+a*2]=money1[x][x+a]+money2[x+a+1][x+a*2];
}
for(x=1;x<=n;x++)
for(a=1;a<=n;a++)
	dp[x][a]=-1;
return;
}



int main()
{
//freopen("bus.in","rt",stdin);
pre();
z(1,k-1);

printf("%d\n",dp[1][k-1]);

return 0;
}


void z(int start,int lef)
{
dp[start][lef]=1000;
int d=0,e=0,end=0;
if(lef==1)
	   {dp[start][lef]=money[start][n];return;}

int grr=(n-start)/2;

while(grr>0)
{

if(start+e+grr<=n)
{
if(dp[start+e+grr][lef-1]==-1)z(start+e+grr,lef-1);

if( money[start][start+e+grr] + dp[start+e+grr][lef-1] < dp[start][lef])
   {
   dp[start][lef]=money[start][start+e+grr]+dp[start+e+grr][lef-1];
   e+=grr;
   }
}

if(e>=grr)
{
if(dp[start+e-grr][lef-1]==-1)z(start+e-grr,lef-1);

if( money[start][start+e-grr] + dp[start+e-grr][lef-1] < dp[start][lef])
   {
   dp[start][lef]=money[start][start+e-grr]+dp[start+e-grr][lef-1];
   e-=grr;
   }
}
grr/=2;
}

return;
}

/*
for(d=12;d>=0;d--)
{
if(e+p2[d]<=n-start&&dp[start+e+p2[d]][lef-1]==-1)
z(start+e+p2[d],lef-1);

if(e+p2[d]<=n-start&&
   money[start][ start+e+p2[d] ] + dp[start+e+p2[d]][lef-1] < dp[start][lef])
   {dp[start][lef]=money[start][ start+e+p2[d] ] + dp[start+e+p2[d]][lef-1];
   e+=p2[d];
   }
   
if(e-p2[d]>=0&&dp[start+e-p2[d]][lef-1]==-1)
z(start+e-p2[d],lef-1);

if(e-p2[d]>=0&&
   money[start][ start+e-p2[d] ] + dp[start+e-p2[d]][lef-1] < dp[start][lef])
   {dp[start][lef]=money[start][ start+e-p2[d] ] + dp[start+e-p2[d]][lef-1];
   e-=p2[d];
   }
}
*/

/*
return 0;
}
*/











//DP - argumentite sa kolko spriki sa izpolzvani i dokyde stiga poslednata
//O(K*N) = O(N^2)
// *logN ?
