#include<bits/stdc++.h>
#define ll long long
#define rep(i,aaa,bbb) for(int i=(aaa);i<=(bbb);i++)
#define per(i,aaa,bbb) for(int i=(aaa);i>=(bbb);i--)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define pii pair<int,int>
#define l first
#define r second
#define ptln(...) print(__VA_ARGS__,"\n")
using namespace std;

template<typename T>inline void read(T&x){cin>>x;}
template<typename T,typename...Args>inline void read(T&x,Args&...args){read(x);read(args...);}
template<typename T>inline void print(const T&x){cout<<x;}
template<typename T,typename...Args>inline void print(const T&x,Args&&...args){cout<<x<<" ";print(args...);}

constexpr int inf=0x7fffffff;
constexpr int maxn=3000+10;

int n,m;
int sx[maxn];

ll F[maxn][maxn];

int Q[maxn],L=1,R=0;
int q[maxn],l=1,r=0;

#define X(j) (sx[j])
#define Y(j) (sx[j]*sx[j]+ F[k-1][j])
#define K(i) (2*sx[i])

int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	read(n,m);
	rep(i,1,n)read(sx[i]),sx[i]+=sx[i-1];
	rep(k,1,m){
		l=1,r=0;
		rep(i,k,n){
			while(L<R && (Y(Q[L+1])- Y(Q[L]))<=K(i)* (X(Q[L+1])- X(Q[L])))L++;
			int j=Q[L];
			F[k][i]=F[k-1][j]+ (sx[i]- sx[j])* (sx[i]- sx[j]);
			while(l<r && (X(q[r])- X(q[r-1]))* (Y(i)- Y(q[r]))<=(Y(q[r])- Y(q[r-1]))* (X(i)- X(q[r])))r--;
			q[++r]=i;
//			ptln("L,R",L,R,"F",F[k][i],"l,r",l,r,"j",j);
		}
		swap(Q,q),swap(L,l),swap(R,r);
	}
	print(m*F[m][n]-sx[n]*sx[n]);
	return 0;
}

/*
5 2
1 2 5 8 6
*/