/*
TASK:bus
LANG:C
*/

#include <stdio.h>
//#include <time.h>

short N, K, c[1000], prev[1000][1000];
long 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 long v1[1000][1000], v2[1000][1000];
  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]+(long long)d*(long long)c[j];
    }
    for(j=d; j<N; ++j)
    {
      i=j-d;
      v2[i][j]=v2[i+1][j]+(long long)d*(long long)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;
  for(i=0; i<N; ++i)
    for(j=0; j<K; ++j)
    {
      dp[i][j]=50000000000000000ll;
      prev[i][j]=j-1;
    }
  dp[0][0]=0;
  for(i=1; i<N; ++i)
    for(j=1; j<K; ++j)
      for(p=prev[i-1][j]; p<i; ++p)
        if(dp[p][j-1]+val[p][i]<dp[i][j])
        {
          dp[i][j]=dp[p][j-1]+val[p][i];
          prev[i][j]=p;
        }
}

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

