/*
LANG:C++
TASK:bus
*/
#include <stdio.h>
#include <string.h>
#include <stack>
#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

struct type {
       int from,k;
       type() {}
       type(int _from,int _k) {
                from = _from;
                k = _k;
       }
};

std::stack<type> st;

int sum[maxn][maxn];
int dp[maxn][maxn];
int root[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;
}

void solve(int rf,int rk) {
     st.push(type(rf,rk));
     while(!st.empty()) {
                        
          type f = st.top();
          int from = f.from;
          int k = f.k;
          
          if(from == n) {
             st.pop();
             root[from][k] = n;
             dp[from][k] = 0;
             continue;
          }
          
          //printf("%d %d %d\n",from,k,dp[from][k]);
          if(dp[from][k] != -1) {
             st.pop();
             continue;
          }
          
          if(k==0) {
             st.pop();
             int res = getS(from, n);
             root[from][k] = n;
             dp[from][k] = res;
             continue;
          }
          
          if(dp[from+1][k-1] == -1) {
             st.push(type(from+1,k-1));
             continue;
          }
          
          int res = getS(from,n);
          int croot = from;
          bool tf(true);
          for(int i=from+1;i<=root[from+1][k-1];i++) {
              if(dp[i][k-1] == -1) {
                 st.push(type(i,k-1));
                 tf = false;
              }
              int next = dp[i][k-1] + getS(from,i);
              if(res > next) {
                     res = next;
                     croot = i;
              }
          }
          if(tf) {
                 st.pop();
                 root[from][k] = croot;
                 dp[from][k] = res;
          }
     }
}

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

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