/*
TASK:bus
LANG:C++
*/
#include<stdio.h>
//#define min(a,b) (a<b?a:b)
#define MAX 30
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];


int z(int start,int left);

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<=n;a++)
{
money[x][x+a*2]=money1[x][x+a]+money2[x+a+1][x+a*2];
money[x][x+a*2+1]=money1[x][x+a]+money2[x+a+1][x+a*2+1];
}
return;
}


int main()
{
freopen("bus.in","rt",stdin);
pre();

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

z(1,k-1);

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

return 0;
}

int z(int start,int left)
{
int d,e=0,min=10000000;
if(left==1)
           {dp[start][left]=money[start][n];return 0;}
for(d=12;d>=0;d--)
{
if(e+p2[d]<=n-start&&dp[start+e+p2[d]][left-1]==-1)
z(start+e+p2[d],left-1);

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

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

dp[start][left]=min;
return 0;
}
