// Lagrangian Relaxation & Li Chao Tree

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e18

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N+1),pf(N+1);
	for(int i=0;i<N;i++){
		cin>>v[i];
		pf[i+1]=pf[i]+v[i];
	}
	auto solve=[&](int y)->pair<int,int>{
		vector<int>dp(N+1,INF),cnt(N+1),t((N+1)*4);
		auto cost=[&](int s,int e)->int{
			return dp[s]+(pf[e]-pf[s])*(e-s);
		};
		auto add=[&](int i,int l,int r,int p)->void{
			while(true){
				int m=(l+r)/2;
				bool ll=cost(p,l)<cost(t[i],l);
				bool mm=cost(p,m)<cost(t[i],m);
				if(mm){
					swap(t[i],p);
				}
				if(l==r){
					break;
				}
				if(ll!=mm){
					i=i*2+1;
					r=m;
				}
				else{
					i=i*2+2;
					l=m+1;
				}
			}
		};
		auto get=[&](int i,int l,int r,int x)->int{
			int bc=INF,bi=0;
			while(true){
				int m=(l+r)/2;
				int c=cost(t[i],x);
				if(c<bc){
					bc=c;
					bi=t[i];
				}
				if(l==r){
					break;
				}
				if(x<m){
					i=i*2+1;
					r=m;
				}
				else{
					i=i*2+2;
					l=m+1;
				}
			}
			return bi;
		};
		dp[0]=-y;
		cnt[0]=-1;
		add(0,0,N,0);
		for(int i=1;i<=N;i++){
			int o=get(0,0,N,i);
			dp[i]=cost(o,i)+y;
			cnt[i]=cnt[o]+1;
			add(0,0,N,i);
		}
		return{dp[N],cnt[N]};
	};
	int l=0,h=INF;
	while(l<h){
		int m=(l+h)/2;
		auto [x,c]=solve(m);
		if(c<=K){
			h=m;
		}
		else{
			l=m+1;
		}
	}
	auto [x,c]=solve(h);
	cout<<x-c*h<<'\n';
	return 0;
}