#include<bits/stdc++.h>

#define N 3005

typedef long long ll;

int n,m,l,r,d[N],q[N];

ll f[N][N],s[N];

inline double slope(int i,int x,int y){

    return 1.0*(f[i][x]+s[x]*s[x]-f[i][y]-s[y]*s[y])/(s[x]-s[y]);

}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    n=read();m=read();

    for(int i=;i<=n;i++)d[i]=read();

    for(int i=;i<=n;i++)s[i]=s[i-]+d[i];

    memset(f,0x3f,sizeof(f));f[][]=;

    for(int i=;i<=m;i++){

        l=;r=;

        for(int j=;j<=n;j++){

            for(;l<r&&slope(i-,q[l],q[l+])<*s[j];l++);

            f[i][j]=f[i-][q[l]]+(s[j]-s[q[l]])*(s[j]-s[q[l]]);

            for(;l<r&&slope(i-,q[r],q[r-])>slope(i-,q[r],j);r--);

            q[++r]=j;

        }

    }

    printf("%d\n",m*f[m][n]-s[n]*s[n]);

    return ;

}