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

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

using namespace std;

#define MAXN 1024

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

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

void add() {
    while (nnode) {
        t[nnode].num += value;
        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 = t[node].num = 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);
    //printf("constructed tree\n");
    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];
    }
    //printf("added all\n");
    memset(dp, 127 , sizeof(dp));
    
    dp[1][1] = 0;
    long long oh;
    int len;
    
    //cout <<gatherRight(1, 4, 7) << endl;
    
    for (int k = 2; k <= K; k++) {
        for (int n = k; n <= N; n++) {
            dp[k][n] = dp[k-1][n-1];
            for (int prev = 1; prev < n; prev++) {
                len = n - prev - 1;
                if (len % 2 == 0) {
                    len /= 2;
                    oh = gatherLeft(1, prev, prev+len) + gatherRight(1, prev+len+1, n);
                }
                else {
                    len /= 2;
                    oh = gatherLeft(1, prev, prev+len+1) + gatherRight(1, prev+len+2, n);
                }     
                dp[k][n] = min(dp[k][n], dp[k-1][prev] + oh);
            }
        }
    }
    /*
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    cout << dp[K][N] << endl;
    
    return 0;
}
