#include<cstdio>

 const int MAXN=3e3+;

 int n,m;

 int s[MAXN];

 int q[MAXN],l,r;

 long long f[MAXN][MAXN];

 double count_y(int k,int j){return f[k][j-]+s[k]*s[k];}

 double count(int t,int k,int j){return (count_y(t,j)-count_y(k,j))/(s[t]-s[k]);}

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i)

     {

         int x;

         scanf("%d",&x);

         s[i]=s[i-]+x;

     }

     for(int i=;i<=n;++i)f[i][]=s[i]*s[i];

     for(int j=;j<=m;++j)

     {

         l=,r=;

         for(int i=;i<=n;++i)

         {

             while(l<r&&count(q[l],q[l+],j)<*s[i])++l;

             int temp=q[l];

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

             while(l<r&&count(q[r],i,j)<count(q[r-],q[r],j))--r;

             q[++r]=i;

         }

     }

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

     return ;

 }