#include<bits/stdc++.h>

#define N 100006

#define M 205

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int n,k,a[N],q[N];

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

double slope(int i,int j)

{

    if(s[i]==s[j]) return -1e18;

    return 1.00*((g[i]-s[i]*s[i])-(g[j]-s[j]*s[j]))/(s[j]-s[i]);

}

int main()

{

    // setIO("input");

    int i,j;

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

    for(i=1;i<=n;++i) scanf("%lld",&s[i]),s[i]+=s[i-1];

    for(j=1;j<=k;++j)

    {

        int head=1,tail=0;

        q[++tail]=0;

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

        {

            while(head<tail&&slope(q[head],q[head+1])<=s[i]) ++head;

            f[i]=g[q[head]]+s[q[head]]*(s[i]-s[q[head]]);

            while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) --tail;

            q[++tail]=i;

        }

        memcpy(g,f,sizeof(g));

    }

    printf("%lld\n",f[n]);

    //     for(int x=n,i=k;i>=1;--i) x=pre[x][i], printf("%d ",x);

    return 0;

}