#include <bits/stdc++.h>
#define int long long
using namespace std; 
const int MAXN=3005;
int dp[MAXN][MAXN],sum[MAXN],a[MAXN],n,m,q[MAXN];
int getUp(int u,int j,int k){
	return dp[u][j]-dp[u][k]+sum[j]*sum[j]-sum[k]*sum[k];
}
int getdown(int j,int k){
	return sum[j]-sum[k];
}
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	int head,tail;
	dp[0][0]=0;
	for(int i=1;i<=n;i++) dp[1][i]=sum[i]*sum[i];
    for(int p=2;p<=m;p++){
        head=1,tail=0;
        for(int i=1;i<=n;i++){ 
            while(head<tail&&getUp(p-1,q[head],q[head+1])>2*sum[i]*getdown(q[head],q[head+1])) head++;
            int j=q[head];
            dp[p][i]=dp[p-1][j]+(sum[j]-sum[i])*(sum[j]-sum[i]); 
            while(head<tail&&getUp(p-1,q[tail-1],q[tail])*getdown(q[tail],i)<getUp(p-1,q[tail],i)*getdown(q[tail-1],q[tail])) tail--;
            q[++tail]=i;
        }
    }
    int ans=m*dp[m][n]-sum[n]*sum[n];
    printf("%lld",ans);
	return 0;
}