#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18, N = 50001;

int n, k;
int a[N], pref[N];
int dp[N][2];

void calc(int l, int r, int L, int R, int j)
{
    if(l > r) return;
    int m = (l+r) / 2;
    dp[m][j] = INF;
    int M = 0;
    int c = j^1;
    for(int i = L; i <= min(R, m-1); i++)
    {
        int val = dp[i][c] + (pref[m] - pref[i]) * (m-i);
        if(val < dp[m][j])
        {
            dp[m][j] = val;
            M = i;
        }
    }
    calc(l, m-1, L, M, j);
    calc(m+1, r, M, R, j);
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
	cin >> n >> k;
    k++;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i][1] = INF;
    }
    for(int j = 1; j <= k; j++)
    {
        calc(1, n, 0, n, j%2);
    }
    cout << dp[n][k%2];
}