/*
TASK: bus
LANG: C++
*/

#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <cstdlib>
#define MAX 1024

using namespace std;

FILE *in; FILE *out;

int n, m;
int a[MAX];
int dyn[MAX][MAX];
int sm[MAX][MAX];
int prc[MAX][MAX];


void precalc(void)
{
int i, c;
int sum, mid;

for (i=0; i<n; i++)
    {
    sum = 0; for (c=i; c>0; c--) {sum += a[c] * (i - c); sm[i][c] = sum;}
    sum = 0; for (c=i; c<n; c++) {sum += a[c] * (c - i); sm[i][c] = sum;}
    }

for (i=0; i<n; i++) for (c=i+1; c<n; c++) {mid = (i + c)/2; prc[i][c] = sm[i][mid] + sm[c][mid+1];}

return;
}


int recurse(int pos, int rem)
{
int i;
int cur, ans;

if (pos >= n-2) return 0;
if (dyn[pos][rem] != -1) return dyn[pos][rem];

ans = 1500000001;


if (rem == 0) ans = prc[pos][n-1]; 
else
   {
   for (i=pos+1; i<n; i++)
       {
       cur = recurse(i, rem-1) + prc[pos][i];
       if (cur < ans) ans = cur;
       }
   }

dyn[pos][rem] = ans;
return ans;
}


int main(void)
{
int i;

memset(a, 0, sizeof(a));
memset(dyn, -1, sizeof(dyn));
memset(sm, 0, sizeof(sm));
memset(prc, 0, sizeof(prc));

//in = fopen("bus.in", "rt"); out = fopen("bus.out", "wt");
in = stdin; out = stdout;

fscanf(in, "%d %d", &n, &m);
for (i=0; i<n; i++) fscanf(in, "%d", &a[i]);

precalc();
fprintf(out, "%d\n", recurse(0, m-2));

//system("pause");

return 0;
}
