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

#define int long long

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 cost=[&](int s,int e)->int{
		return (pf[e]-pf[s])*(e-s);
	};
	// if(1){
		// N=15;
		// v.resize(N+1),pf.resize(N+1);
		// for(int i=0;i<N;i++){
			// v[i]=rand()%100;
			// pf[i+1]=pf[i]+v[i];
		// }
		// for(int i=1;i<=N;i++){
			// for(int j=1;j<=N;j++){
				// cout<<setw(4)<<cost(i,j)<<' ';
			// }
			// cout<<'\n';
		// }
		// return 1;
	// }
	auto solve=[&](int y)->pair<int,int>{
		vector<int>dp(N+1,1e18),cnt(N+1);
		dp[0]=-y;
		cnt[0]=-1;
		for(int i=1,o=0;i<=N;i++){
			for(int j=o;j<i;j++){
				int x=dp[j]+cost(j,i)+y;
				if(x<dp[i]){
					dp[i]=x;
					cnt[i]=cnt[j]+1;
					o=j;
				}
			}
		}
		return{dp[N],cnt[N]};
	};
	int l=0,h=1e12;
	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;
}