LEAVES

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define task "LEAVES"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 2;
const ll Inf = 1e9;
int n, k, last[15];
ll a[N], d[N], f[N];
ll dp[N][15];
vector<int> line[15];
vector<ld> point[15];

void Read(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
        d[i] = d[i - 1] + a[i],
        f[i] = f[i - 1] + a[i] * i,
        cout << a[i] << " ";
    cout << "\n";
}

/// dp(i, t) = d(j) * (-i) + dp(j, t - 1) + f(j) + [ i * d(i) - f(i) ]
/// Có thể coi [i * d(i) - f(i)] là 1 hằng số tăng vì nó phụ thuộc vào i và đổi với mi j, do vậy bài này là dp convex

ld ff(int t, int i, int j){
    return (ld) 1.0 * (dp[i][t] + f[i] - dp[j][t] - f[j]) / (d[j] - d[i]);
}

void Solve(){
    fill_n(&dp[0][0], N * 15, Inf);
    dp[0][0] = 0;
    line[0].push_back(0);
    for(int i = 0; i <= k; ++i)
        point[i].push_back(-Inf);
    for(int i = 1; i <= n; ++i){
        for(int j = min(i, k); j; --j){
            while(last[j - 1] < point[j - 1].size() && point[j - 1][last[j - 1]] < -i)
                ++last[j - 1];
            --last[j - 1];
            dp[i][j] = d[line[j - 1][last[j - 1]]] * (-i) + d[i] * i - f[i] +
                       f[line[j - 1][last[j - 1]]] + dp[line[j - 1][last[j - 1]]][j - 1];
            while(line[j].size() > 1){
                if(ff(j, i, line[j][line[j].size() - 1]) <= ff(j, i, line[j][line[j].size() - 2])){
                    line[j].pop_back();
                    point[j].pop_back();
                    continue;
                }
                break;
            }
            last[j] = min(last[j], (int)point[j].size() - 1);
            if(line[j].size())
                point[j].push_back(ff(j, i, line[j].back()));
            line[j].push_back(i);
        }
    /*  cout << i << ": ";
        for(int j = 1; j <= k; ++j)
            cout << dp[i][j] << " ";
        cout << "\n";
        for(int i = 1; i <= k; ++i){
        cout << " " << i << ": ";
        for(auto j : line[i])
            cout << j << " ";
        cout << "\n";
    }
        //cout << "\n";*/
    }
    cout << dp[n][k];

}

void Bruteforces(){
    fill_n(&dp[0][0], N * 15, Inf);
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i){
        cout << "\n" << i << ": ";
        for(int t = 1; t <= k; ++t){
            for(int j = 0; j < i; ++j)
                dp[i][t] = min(dp[i][t], dp[j][t - 1] + (d[i] - d[j]) * i - (f[i] - f[j]));
            cout << dp[i][t] << " ";
        }
    }
    cout << dp[n][k];
}

main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    Read();
    Solve();
    //Bruteforces();
}