#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 200002;
const ll INF = 1e18;

int n, k;
ll a[MAXN], pref[MAXN], dp[MAXN], used[MAXN];

struct Point {
    ll a = -1;

    Point() {}

    Point(int x) {
        a = x;
    }

    ll f(ll b) {
        if (a == -1) return INF;
        return (pref[b] - pref[a]) * (b - a) + dp[a];
    }

    bool operator<(const Point &x) const {
        return true;
    }
};

Point tree[4*MAXN];

void add(Point p, int v = 1, int tl = 0, int tr = n+1) {
    int tm = (tl + tr) / 2;
    bool lef = p.f(tl) < tree[v].f(tl);
    bool mid = p.f(tm) < tree[v].f(tm);
    if (mid) swap(p, tree[v]);

    if (tl + 1 != tr) {
        if (lef != mid) {
            add(p, v*2, tl, tm);
        } else {
            add(p, v*2+1, tm, tr);
        }
    }
}

pair<ll, Point> get(int b, int v = 1, int tl = 0, int tr = n+1) {
    int tm = (tl + tr) / 2;
    pair<ll, Point> x = {tree[v].f(b), tree[v]};
    if (tl + 1 == tr) {
        return x;
    } else {
        if (b < tm) {
            return min(x, get(b, v*2, tl, tm));
        } else {
            return min(x, get(b, v*2+1, tm, tr));
        }
    }
}

pair<ll, ll> solve(ll lambda) {
    fill(tree, tree+4*MAXN, Point(-1));
    add(Point(0));
    for (int i = 1; i <= n; i++) {
        auto opt = get(i);
        dp[i] = opt.first + lambda;
        used[i] = used[opt.second.a] + 1;
        add(Point(i));
    }
    return {dp[n], used[n]};
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k; k++;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = a[i] + pref[i-1];
    }
    ll lo = 0, hi = 1e17;
    while (lo < hi) {
        ll lambda = (lo + hi) / 2;
        auto x = solve(lambda);
        if (x.second <= k) hi = lambda;
        else lo = lambda + 1;
    }
    auto ans = solve(lo);
    cout << (ans.first - lo * ans.second) << "\n";
    return 0;
}