/*
LANG:C++
TASK:bus
*/
#include <stdio.h>
#include <string.h>
#define min(a,b) (a < b ? a : b)
#define FOR(i,n) for(int i=0;i<n;i++)
#define maxval 9999999
#define maxn 1024

int dp[maxn][maxn];
int C[maxn];
int n,k;

int abs(int x) {
    if(x<0) return -x;
    return x;
}
int solve(int from,int k) {
     if(dp[from][k] != maxval) return dp[from][k];
     // vyv from ima bus station
     if(k == 0) {
          // everything to the end is here or in the end
          int cres = 0;
          for(int i=from+1;i<=n;i++) {
             int i1,i2;
             i1 = i - from;
             i2 = n - i;
             cres += min( C[i] * i1, C[i] * i2 );
          }
          return dp[from][k] = cres;
     }
     // end it now
     int res = maxval;
     int cres(0);
     for(int i=from+1;i<=n;i++) {
             int i1,i2;
             i1 = i - from;
             i2 = n - i;
             cres += min( C[i] * i1, C[i] * i2 );
     }
     
     res = min(res, cres);
     
     // split
     for(int i=from+1;i<n;i++) {
             int cur = 0;
             for(int j = from+1; j < i; j++){
                     int i1 = j-from;
                     int i2 = i-j;
                     cur += min( C[j] * i1, C[j] * i2);
             }
             int next = solve(i, k-1) + cur;
             // 
             res = min(res, next);
     }
     return dp[from][k] = res;
}

void init() {
     scanf("%d%d",&n,&k);
     FOR(i,n) scanf("%d",&C[i+1]);
}

int main() {
    init();
    FOR(i,n+1) FOR(j,k+1) dp[i][j] = maxval;
    printf("%d\n", solve(1,k-2));
    scanf("%d",&n);
    return 0;
}
