#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=3005;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int n,m;
int a[maxn],sum[maxn];
inline ll w(int l,int r){
    return 1ll*(sum[n]-m*(sum[r]-sum[l]))*(sum[n]-m*(sum[r]-sum[l]));
}
ll f[maxn][maxn];
void solve(int i,int l1,int r1,int l2,int r2){
    if(l1>r1) return;
    int mid=(l1+r1)>>1;
    int x=0;
    for(int j=l2;j<=min(mid,r2);++j){
        if(f[i-1][j]+w(j,mid)<f[i][mid]) f[i][mid]=f[i-1][j]+w(j,mid),x=j;
    }
    if(l1==r1) return;
    solve(i,l1,mid-1,l2,x),solve(i,mid+1,r1,x,r2);
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i];
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i) f[1][i]=w(0,i);
    for(int i=2;i<=m;++i) solve(i,1,n,1,n);
    printf("%lld\n",f[m][n]/m);
    return 0;
}