/*
TASK:bus
LANG:C
*/

#include <stdio.h>

short N, K, c[1000];
long dp[1000][1000], val[1000][1000];

void input(void)
{
  short i;
  FILE *fp;
  fp=stdin;//fopen("bus.in", "rt");
  fscanf(fp, "%hd %hd", &N, &K);
  for(i=0; i<N; ++i)
    fscanf(fp, "%hd", &c[i]);
  //fclose(fp);
}

void calcVal(void)
{
  short i, j, d;
  static long v1[1000][1000], v2[1000][10000];
  for(i=0; i<N; ++i)
    v1[i][i]=v2[i][i]=val[i][i]=0;
  for(d=1; d<N; ++d)
  {
    for(i=0; i<N-d; ++i)
    {
      j=i+d;
      v1[i][j]=v1[i][j-1]+d*c[j];
    }
    for(j=d; j<N; ++j)
    {
      i=j-d;
      v2[i][j]=v2[i+1][j]+d*c[i];
    }
  }
  for(i=0; i<N; ++i)
    for(j=i+1; j<N; ++j)
      val[i][j]=v1[i][(i+j)/2]+v2[(i+j)/2+1][j];
}

void calcDP(void)
{
  short i, j, p;
  long s;
  for(i=0; i<N; ++i)
    for(j=0; j<K; ++j)
      dp[i][j]=1000000;
  dp[0][0]=0;
  for(i=1; i<N; ++i)
    for(j=1; j<K; ++j)
      for(p=j-1; p<i; ++p)
        if(dp[p][j-1]+val[p][i]<dp[i][j])
          dp[i][j]=dp[p][j-1]+val[p][i];
}

int main(void)
{
  input();
  calcVal();
  calcDP();
  printf("%ld\n", dp[N-1][K-1]);
  return 0;
}

