#include <bits/stdc++.h>

using namespace std;
#define int long long int

int n,k;
int t[100010];
int ans;
vector<int> dp;
deque<int> st;
vector<int> sums;
vector<int> db;

int sum(int x,int y) {
    return(sums[y]-sums[x-1]);
}

int a,b;
int log_search(int x,int y) {
    if (x==y) {
        return(x);
    }
    int koz=(x+y)/2;
    if ( dp[a]+sum(a+1,koz)*(koz-a) <= dp[b]+sum(b+1,koz)*(koz-b) ) {
        return(log_search(koz+1,y));
    } else {
        return(log_search(x,koz));
    }
}

int solve(int l) {
    int kor,kes;
    dp.assign(n+1,0);
    db.assign(n+1,0);
    st.clear();
    dp[0]=0;
    db[0]=0;
    st.push_front(0);
    for (int i=1;i<=n;i++) {
        while ((st.size()>=2) && (dp[st[0]]+sum(st[0]+1,i)*(i-st[0]) >= dp[st[1]]+sum(st[1]+1,i)*(i-st[1])  )) {
            //cout << st[0] << " " << dp[st[0]] << " " << st[1] << " " << st[st[1]] << " " << sum(st[0]+1,i) << " " << sum(st[1]+1,i) << endl;
            st.pop_front();
        }
        dp[i]=l+sum(st[0]+1,i)*(i-st[0])+dp[st[0]];
        db[i]=db[st[0]]+1;
        while (i<n) {
            if (st.size()<=1) {
                break;
            }
            a=st[st.size()-1]; b=i;
            kes=log_search(b+1,n+1);
            a=st[st.size()-2]; b=st[st.size()-1];
            kor=log_search(b+1,n+1);
            if (kes<=kor) {
                st.pop_back();
            } else {
                break;
            }
        }
        st.push_back(i);
    }
    ans=dp[n]-db[n]*l;
/*
    if (k==db[n]-1) {
        for (int i=0;i<=n;i++) {
            cout << dp[i] << " " << db[i] << endl;
        }
    }
*/
    return(db[n]-1);
}

int bin_ker(int x,int y) {
    

    int z=solve((x+y)/2);
    if (z==k) {
        return(ans);
    }
    if (z<k) {
        return(bin_ker(x,(x+y)/2-1));
    } else {
        return(bin_ker((x+y)/2+1,y));
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        cin >> t[i];
    }
    sums.assign(n+1,0);
    for (int i=1;i<=n;i++) {
        sums[i]=sums[i-1]+t[i];
    }
    cout << bin_ker(0,1e17) << endl;
    return(0);
}