#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
int n,m,a[3010],sum[3010],q[3010],f[3010][3010];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
double slop(int j,int k,int x){return (double)(f[j][x]-f[k][x]+sum[j]*sum[j]-sum[k]*sum[k])/(sum[j]-sum[k]);}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  memset(f,10,sizeof(f));
	for(int i=1;i<=n;++i)  a[i]=read();
	for(int i=1;i<=n;++i)  sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;++i)  f[i][1]=sum[i]*sum[i];
	for(int j=2;j<=m;++j){
		int head=0,tail=0;
		for(int i=1;i<=n;++i){
			while(head<tail&&slop(q[head],q[head+1],j-1)<(double)sum[i]*2)  ++head;
			int temp=q[head];  f[i][j]=f[temp][j-1]+(sum[i]-sum[temp])*(sum[i]-sum[temp]);
			while(head<tail&&slop(q[tail],q[tail-1],j-1)>slop(i,q[tail],j-1))  --tail;
			q[++tail]=i;
		}
	}
	printf("%d\n",f[n][m]*m-sum[n]*sum[n]);
	return 0;
}