#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 100010;
const int MAXK = 11;

ll dp[MAXK][MAXN];
ll w[MAXN];
ll s[MAXN];
ll p[MAXN];
int Q[MAXN];

ll cost(int i,int j){
    return ((long long)j)*(s[i] - s[j+1])+p[j+1]-p[i];
}

ll g(int k,int l,int j){
    return (dp[k+1][j-1] - dp[l+1][j-1]+((long long)l)*s[l+1]-((long long)k)*s[k+1]-p[l+1]+p[k+1])/((long long)(l-k));
}

int main(){
    int n,K;
    cin >> n >> K;
    for (int i = n ; i >= 1 ; i--){
        cin >> w[i];
        s[i] = s[i+1] + w[i];
        p[i] = p[i+1] + i*w[i];
    }

    for(int j = 1 ; j <= K ; j++){
        dp[n+1][j] = 1LL << 50;
    }

    for(int i = 1 ; i <= n ; i++){
        dp[i][1] = cost(i,n);
    }

    for(int j = 2 ; j <= K ; j++){
        dp[n][j] = 0LL;
        int head = 0, tail = 0;
        Q[tail] = n;
        for(int i = n-1 ; i >= 1 ; i--){
            while((tail-head > 0) && (g(Q[head+1],Q[head],j) <= s[i])){
                head++;
            }
            dp[i][j] = cost(i,Q[head]) + dp[Q[head]][j];
            while((tail-head > 0) && (g(i,Q[tail],j) <= g(Q[tail],Q[tail-1],j))){
                tail--;
            }
            tail++;
            Q[tail] = i;
        }
    }

    cout << dp[1][K] << endl;
    return 0;
}