#include <bits/stdc++.h>

using namespace std;

typedef pair<int,long long> PII;

int n,m;
int a[5010];
long long dp[3050][5010];
PII q[6000];
long long f[5010],g[5010];

// 上凸
int check(PII a,PII b,PII c){
	return (a.second-b.second)*(b.first-c.first)<=(b.second-c.second)*(a.first-b.first);
}

int main(){
	while (scanf("%d%d",&n,&m)!=EOF){
		f[0]=g[0]=0;
		for (int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			f[i]=f[i-1]+a[i]*i;
			g[i]=g[i-1]+a[i];
			dp[1][i]=f[i];
		}
		for (int i=2;i<=m;i++){
			int qh=0;
			int qt=1;
			//dp[i][1]=a[i];
			q[qt]=PII(0,0);
			//q[qt]=PII(1,dp[i][1]-f[1]+g[1]);
			for (int j=1;j<=n;j++){
				while (qh+1<qt && q[qh].second-g[j]*q[qh].first>q[qh+1].second-g[j]*q[qh+1].first) qh++;
				dp[i][j]=q[qh].second-g[j]*q[qh].first+f[j];
				PII x = PII(j, dp[i-1][j]-f[j]+g[j]*j);
				while (qh<qt-1 && check(x,q[qt-1],q[qt-2])) qt--;
				q[qt++]=x;
			}
		}
		/*
		for (int i=1;i<=m;i++){
			for (int j=1;j<=n;j++){
				cout << dp[i][j]<<" ";
			}
			cout<<endl;
		}
		*/
		printf("%lld\n",dp[m][n]);
	}
	return 0;
}