Cancer

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)

using namespace std;
typedef long long ll;
const int mxn = 2e5;

int n, k;
ll a[mxn];
ll pre[mxn];


ll dp[mxn];
int cn[mxn];

void f(ll lambda){
	dp[0] = 0;
	cn[0] = 0;
	int l = 1;
	fr(i, 1, n+1){
		ll mi = 2e18;
		fr(j, l, i+1){
			ll cv = dp[j-1] + (pre[i]-pre[j-1])*(i-j) + lambda;
			if(cv < mi){
				mi = cv;
				l = j;
				cn[i] = cn[j-1]+1;
			}
			else if(cv == mi){
				if(cn[j-1]+1 <= cn[i]) l = j;
				cn[i] = min(cn[i], cn[j-1]+1);
			}

		}
		dp[i] = mi;
	}
}

ll solve(){
	ll l = 0, r = 1e18;
	ll ans = 0;
	while(l < r){
		ll mid = (l+r)/2;
		f(mid);
		if(cn[n] > k){
			ans = mid;
			l = mid+1;
		}
		else{
			r = mid;
		}
	}
	++ans;
	f(ans);
	return dp[n]-k*ans;
}



int main(){
	cin >> n >> k;
	fr(i, 1, n+1){
		cin >> a[i];
	}
	fr(i, 1, n+1){
		pre[i] = pre[i-1] + a[i];
	}
	cout<<solve();
}