//N,K<1e5, meaning that the final answer might overflow long long
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif
const ll maxn=1e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifndef WIN32
#define int __int128
#define ll __int128
#define getchar getchar_unlocked
#endif
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
const int inf=4'000'000'000'000'000'000'000;
ll arr[maxn];
ll dp[maxn],cnt[maxn];
deque<ii> dq; //transition point, start time
ll n,k;
ll W(ll i, ll j){
    return (j-i+1)*(arr[j]-arr[i-1]);
}
ll solve(ll cost){
    memset(dp,0,sizeof(dp)),memset(cnt,0,sizeof(cnt));
    dq.clear();
    for (int i=1;i<=n;i++){
        if (dq.size()>=2 && dq[0].second==dq[1].second) dq.pop_front(); //the time has come
        while (dq.size() && dp[dq.back().first-1]+W(dq.back().first,dq.back().second) >
                dp[i-1]+W(i,dq.back().second)){ // covers entire segment
            dq.pop_back(); //if transitioning at i beats out current
        }
        if (dq.empty()){ //if there is nothing
            dq.emplace_back(i,i); //starting now
        } else{ // we have some segment {point, start}, we are at curr > point
        //need to find a time X > start, such that dp[point-1]+W(point,X)>=dp[curr-1]+W(curr,X)
            ll l=dq.back().second,r=n+1,m; //find where it is optimal to cut dp[1..i-1] + W[i..r]
            while (l+1<r){
                m=(l+r)>>1;
                if (dp[dq.back().first-1]+W(dq.back().first,m)>dp[i-1]+W(i,m)){
                    r=m; //win, move towards left
                } else l=m; //lose, move towards right
            }
            if (r!=n+1){
                dq.emplace_back(i,r);
            }
        }
        dp[i]=W(dq.front().first,i)+dp[dq.front().first-1]+cost; // dp[1..X-1] + W[X..Y] + cost
        cnt[i]=cnt[dq.front().first-1]+1; //number of segments taken
        if (dq.front().second==i) dq.front().second++; //update index to next one
    }
    return cnt[n];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    n=read(),k=read();
    for (int i=1;i<=n;i++){
        arr[i]=read();
        arr[i]+=arr[i-1];
    }
    ll l=0,r=inf,m;
    ll ans=0;
    while (l!=r-1){
        m=(l+r)>>1;
        if (solve(m)>k){
            l=m;
        } else{
            ans=dp[n]-k*m;
            r=m;
        }
    }
    print(ans);
    return 0;
}