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

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

#define MAXN 1024

typedef struct node {
    long long costl;
    long long costr;
    int left, right;
}node;

long long dp[2][MAXN];
long long c[MAXN][MAXN];
node t[2*MAXN+2];
int sum[MAXN];
int N, K;
int nnode, value, pos;

void add() {
    while (nnode) {
        t[nnode].costl += abs(t[nnode].left - pos)*value;
        t[nnode].costr += abs(t[nnode].right - pos)*value;
        nnode /= 2;
    }
    return;
}

void construct(int node, int left, int right) {
    t[node].left = left;
    t[node].right = right;
    t[node].costr = t[node].costl = 0;
    if (left >= right) {
        return;
    }
    construct(node*2, left, (left+right)/2);
    construct(node*2+1, (left+right)/2+1, right);
}

long long gatherLeft(int node, int start, int end) {
//    printf("%d %d %d\n", node, start, end);
    if (start > end) {
        return 0;
    }
    if (t[node].left == start && t[node].right == end) {
        return t[node].costl;
    }
    int m = (t[node].left + t[node].right)/2;
    if (m >= end) {
        return gatherLeft(node*2, start, end);
    }
    else if (m < start) {
        return gatherLeft(node*2+1, start, end);
    }
    else {
        return gatherLeft(node*2, start, m) + gatherLeft(node*2+1, m+1, end) + (sum[end] - sum[m])*(m+1-start);
    }
}


long long gatherRight(int node, int start, int end) {
    if (start > end) {
        return 0;
    }
    if (t[node].left == start && t[node].right == end) {
        return t[node].costr;
    }
    int m = (t[node].left + t[node].right)/2;
    if (m >= end) {
        return gatherRight(node*2, start, end);
    }
    else if (m < start) {
        return gatherRight(node*2+1, start, end);
    }
    else {
        return gatherRight(node*2, start, m) + gatherRight(node*2+1, m+1, end) + (sum[m] - sum[start-1])*(end-m);
    }
}


int main() {
    scanf("%d%d", &N, &K);
    
    construct(1, 1, MAXN);

    for (int i = 1; i <= N; i++) {
        scanf("%d", &sum[i]);
        nnode = MAXN+i-1;
        value = sum[i];
        pos = i;
        add();
        sum[i] += sum[i-1];
    }

    memset(dp, 127 , sizeof(dp));
    
    dp[0][1] = 0;
    long long oh;
    int len;
    int flag = 1;
    
    for (int i = 1; i <= N; i++) {
        for (int j = i+1; j <= N; j++) {
            len = j - i - 1;
            if (len % 2 == 0) {
                len /= 2;
                oh = gatherLeft(1, i, i+len) + gatherRight(1, i+len+1, j);
            }
            else {
                len /= 2;
                oh = gatherLeft(1, i, i+len+1) + gatherRight(1, i+len+2, j);
            }
            c[i][j] = oh;
        }
    }
    
    for (int k = 2; k <= K; k++) {
        for (int n = k; n <= N; n++) {
            dp[flag][n] = dp[1-flag][n-1];
            for (int prev = k-1; prev < n; prev++) {
                dp[flag][n] = min(dp[flag][n], dp[1-flag][prev] + c[prev][n]);
            }
        }
        flag = 1 - flag;
    }
    
    cout << dp[1-flag][N] << endl;
    return 0;
}
