#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll INF = (1LL<<60);
 
int n, m;
vector<ll> prefix;
vector<ll> pre_dp, cur_dp;
 
// cost của đoạn [l..r]
inline ll C(int l, int r) {
    ll sum = prefix[r] - (l>0 ? prefix[l-1] : 0);
    ll len = r - l + 1;
    return sum * len;
}
 
void compute(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    pair<ll,int> best = {INF, -1};
    for (int k = optl; k <= min(mid, optr); ++k) {
        ll val = (k ? pre_dp[k-1] : 0) + C(k, mid);
        if (val < best.first) {
            best = {val, k};
        }
    }
    cur_dp[mid] = best.first;
    int opt = best.second;
    compute(l,    mid-1, optl,   opt);
    compute(mid+1, r,     opt,    optr);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    // n = số ô, m = số guard
    cin >> n >> m;
    prefix.resize(n);
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        prefix[i] = x + (i>0 ? prefix[i-1] : 0);
    }
 
    // DP khởi tạo: chỉ 1 guard -> toàn bộ prefix [0..i]
    pre_dp.assign(n, 0);
    for (int i = 0; i < n; i++) {
        pre_dp[i] = C(0, i);
    }
 
    // Chia m guard thành m nhóm liên tiếp
    for (int g = 1; g < m; g++) {
        cur_dp.assign(n, INF);
        compute(0, n-1, 0, n-1);
        pre_dp = cur_dp;
    }
 
    cout << pre_dp[n-1] << "\n";
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwoKY29uc3QgbGwgSU5GID0gKDFMTDw8NjApOwoKaW50IG4sIG07CnZlY3RvcjxsbD4gcHJlZml4Owp2ZWN0b3I8bGw+IHByZV9kcCwgY3VyX2RwOwoKLy8gY29zdCBj4bunYSDEkW/huqFuIFtsLi5yXQppbmxpbmUgbGwgQyhpbnQgbCwgaW50IHIpIHsKICAgIGxsIHN1bSA9IHByZWZpeFtyXSAtIChsPjAgPyBwcmVmaXhbbC0xXSA6IDApOwogICAgbGwgbGVuID0gciAtIGwgKyAxOwogICAgcmV0dXJuIHN1bSAqIGxlbjsKfQoKdm9pZCBjb21wdXRlKGludCBsLCBpbnQgciwgaW50IG9wdGwsIGludCBvcHRyKSB7CiAgICBpZiAobCA+IHIpIHJldHVybjsKICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICBwYWlyPGxsLGludD4gYmVzdCA9IHtJTkYsIC0xfTsKICAgIGZvciAoaW50IGsgPSBvcHRsOyBrIDw9IG1pbihtaWQsIG9wdHIpOyArK2spIHsKICAgICAgICBsbCB2YWwgPSAoayA/IHByZV9kcFtrLTFdIDogMCkgKyBDKGssIG1pZCk7CiAgICAgICAgaWYgKHZhbCA8IGJlc3QuZmlyc3QpIHsKICAgICAgICAgICAgYmVzdCA9IHt2YWwsIGt9OwogICAgICAgIH0KICAgIH0KICAgIGN1cl9kcFttaWRdID0gYmVzdC5maXJzdDsKICAgIGludCBvcHQgPSBiZXN0LnNlY29uZDsKICAgIGNvbXB1dGUobCwgICAgbWlkLTEsIG9wdGwsICAgb3B0KTsKICAgIGNvbXB1dGUobWlkKzEsIHIsICAgICBvcHQsICAgIG9wdHIpOwp9CgppbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShudWxscHRyKTsKCiAgICAvLyBuID0gc+G7kSDDtCwgbSA9IHPhu5EgZ3VhcmQKICAgIGNpbiA+PiBuID4+IG07CiAgICBwcmVmaXgucmVzaXplKG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBsbCB4OwogICAgICAgIGNpbiA+PiB4OwogICAgICAgIHByZWZpeFtpXSA9IHggKyAoaT4wID8gcHJlZml4W2ktMV0gOiAwKTsKICAgIH0KCiAgICAvLyBEUCBraOG7n2kgdOG6oW86IGNo4buJIDEgZ3VhcmQgLT4gdG/DoG4gYuG7mSBwcmVmaXggWzAuLmldCiAgICBwcmVfZHAuYXNzaWduKG4sIDApOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBwcmVfZHBbaV0gPSBDKDAsIGkpOwogICAgfQoKICAgIC8vIENoaWEgbSBndWFyZCB0aMOgbmggbSBuaMOzbSBsacOqbiB0aeG6v3AKICAgIGZvciAoaW50IGcgPSAxOyBnIDwgbTsgZysrKSB7CiAgICAgICAgY3VyX2RwLmFzc2lnbihuLCBJTkYpOwogICAgICAgIGNvbXB1dGUoMCwgbi0xLCAwLCBuLTEpOwogICAgICAgIHByZV9kcCA9IGN1cl9kcDsKICAgIH0KCiAgICBjb3V0IDw8IHByZV9kcFtuLTFdIDw8ICJcbiI7CiAgICByZXR1cm4gMDsKfQo=

NiAzCjExCjExCjExCjI0CjI2CjEwMAo=

6 3
11
11
11
24
26
100