/*
TASK: bus
LANG: C
*/

#include <stdio.h>

#define MAX 1005
#define INF 1000000005

#define MINF(a, b) (((a) < (b)) ? (a) : (b))

void input(void);
void solve(void);

void init_C(void);

int n, m;
int A[MAX];
int F[MAX][MAX];
int C[MAX][MAX];
int C1[MAX][MAX];
int C2[MAX][MAX];

int main(void)
{
    input();
    solve();
    
    return 0;
}

void input(void)
{
     int i;
     
     scanf("%d %d", &n, &m);
     
     for(i = 0; i < n; i++) scanf("%d", &A[i]);
}

void solve(void)
{
    int best, z;
    int i, j, k;
    
    init_C();
    
    F[0][1] = 0;
    for(i = 1; i < n; i++) F[i][1] = INF;
    
    for(j = 2; j <= m; j++)
      for(i = 0; i < n; i++) {
        best = INF;
        for(k = i; k >= 0; k--) {
          z = F[k][j - 1] + C[k][i];
          best = best > z ? z : best;
        }
        F[i][j] = best;
      }
      
    printf("%d\n", F[n - 1][m]);
}

void init_C(void)
{
    int i, j, k;

    /* init C1[][] */
    for(i = 0; i < n; i++) C1[i][i] = 0;
    
    for(k = 2; k <= n; k++)
      for(i = 0; i < n; i++) {
        j = i + k - 1; if(j >= n) break;
        C1[i][j] = C1[i][j - 1] + A[j] * (j - i);
      }
      
    /* init C2[][] */
    for(i = 0; i < n; i++) C2[i][i] = 0;
    
    for(k = 2; k <= n; k++)
      for(i = 0; i < n; i++) {
        j = i + k - 1; if(j >= n) break;
        C2[i][j] = C2[i + 1][j] + A[i] * (j - i);
      }
      
    /* init C[][] */
    for(i = 0; i < n; i++)
      for(j = i; j < n; j++) {
        k = (i + j) / 2; 
        C[i][j] = C1[i][k] + C2[k + 1][j];
      }
}
  
