#include<iostream>
#include<cstring>
#include<cstdio>
#define endl '\n'
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
const int N=3005,V=300005,INF=1e9;
int n,m,a[N],s[N],f[N][N],cnt,v;
struct Line{
	int k,b,id;
	Line(){k=0,b=INF,id=0;}
	Line(int _k,int _b,int _id){k=_k,b=_b,id=_id;}
	int f(int x){return k*x+b;}
}tr[V<<2];
void clear(int p,int pl,int pr)
{
	tr[p]=Line(0,INF,0);
	if(pl==pr)return;
	int mid=(pl+pr)>>1;
	if(tr[ls(p)].id)clear(ls(p),pl,mid);
	if(tr[rs(p)].id)clear(rs(p),mid+1,pr);
}
void update(int p,int pl,int pr,int L,int R,Line g)
{
	if(L<=pl&&pr<=R)
    {
        if(!tr[p].id){tr[p]=g;return;}
        int mid=(pl+pr)>>1;
        if(tr[p].f(mid)>g.f(mid))swap(tr[p],g);
        if(tr[p].f(pl)>g.f(pl))update(ls(p),pl,mid,L,R,g);
        if(tr[p].f(pr)>g.f(pr))update(rs(p),mid+1,pr,L,R,g);
        return;
    }
    int mid=(pl+pr)>>1;
	if(L<=mid)update(ls(p),pl,mid,L,R,g);
	if(R>mid)update(rs(p),mid+1,pr,L,R,g);
}
int query(int p,int pl,int pr,int pos)
{
	if(pl==pr)return tr[p].f(pos);
	int mid=(pl+pr)>>1;
	if(pos<=mid)return min(tr[p].f(pos),query(ls(p),pl,mid,pos));
	else return min(tr[p].f(pos),query(rs(p),mid+1,pr,pos));
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m; 
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i],v=max(v,s[i]);
	memset(f,INF,sizeof(f)); f[0][0]=0;
	for(int i=1;i<=n;i++)f[i][1]=s[i]*s[i];
	for(int l=2;l<=m;l++)
	{
		clear(1,1,v);
		for(int i=1;i<=n;i++)if(i>=l)
		{
			Line g=Line(-2*s[i-1],s[i-1]*s[i-1]+f[i-1][l-1],++cnt);
			update(1,1,v,1,v,g);
			f[i][l]=query(1,1,v,s[i])+s[i]*s[i];
		}
	}
	cout<<f[n][m]*m-s[n]*s[n]<<endl;
	return 0;
}