#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=1;i<=N;i++){
		cin>>v[i];
		pf[i]=pf[i-1]+v[i];
	}
	vector<vector<int>>dp(K+1,vector<int>(N+1,INF));
	vector<vector<int>>p(K+1,vector<int>(N+1));
	dp[0][0]=0;
	for(int i=1;i<=N;i++){
		dp[0][i]=pf[i]*i;
	}
	for(int i=1;i<=K;i++){
		for(int j=i;j<=N;j++){
			auto calc=[&](int k)->int{
				return dp[i-1][k]+(pf[j]-pf[k])*(j-k);
			};
			int l=0,h=j-1;
			while(h-l>=3){
				int m1=l+(h-l)/3;
				int m2=h-(h-l)/3;
				if(calc(m1)<=calc(m2)){
					h=m2;
				}
				else{
					l=m1;
				}
			}
			for(int k=0;k<=j-1;k++){
				int c=calc(k);
				if(c<dp[i][j]){
					dp[i][j]=c;
					p[i][j]=k;
				}
			}
		}
	}
	cout<<dp[K][N]<<'\n';
	return 0;
}