/*
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 sum[maxn][maxn];
int dp[maxn][maxn];
int C[maxn];
int n,k;

int abs(int x) {
    if(x<0) return -x;
    return x;
}

int getS(int from,int to) {
    
    if(sum[from][to] != -1) return sum[from][to];
    
    int cres = 0;
    for(int i=from+1;i<to;i++) {
        int i1,i2;
        i1 = i - from;
        i2 = to - i;
        cres += min( C[i] * i1, C[i] * i2 );
    }
    
    return sum[from][to] = cres;
}

int solve(int from,int k) {
     if(dp[from][k] != -1) return dp[from][k];
     
     int res = getS(from+1,n);

     if(k == 0) return dp[from][k] = res;
          
     // split
     for(int i=from+1;i<n;i++) {
             int next = solve(i,k-1) + getS(from,i);
             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() {
//   printf("Build");
    init();
    FOR(i,maxn) FOR(j,maxn) {
                dp[i][j] = -1;
                sum[i][j] = -1;
    }
    printf("%d\n", solve(1,k-2));
    scanf("%d",&n);
    return 0;
}
