#include <cstdio>
#include <deque>
#include <utility>
using namespace std;
typedef pair<long long,long long> ll;
int n,k; ///n is arr size, k is number of groups to split arr into
long long arr[20005]; ///our original array
long long pre[20005];
long long val, groups; ///for returning value once convex_hull() is called
struct linear_hull{
    deque<ll> dq;
    deque<long long> cuts;
    double intercept (ll i, ll j){
        return ((double)(j.second-i.second))/((double)(i.first-j.first));
    }
    void remove(double i){
        ll _front=dq.front();
        dq.pop_front();
        while (!dq.empty() && intercept(_front,dq.front())<=i){
            _front=dq.front();
            dq.pop_front();
            cuts.pop_front();
        }
        dq.push_front(_front);
    }
    void add(ll i,long long j){
        if (!dq.empty()){
            ll _back=dq.back();
            dq.pop_back();
            while (!dq.empty() && intercept(i,dq.back())<= intercept(_back,dq.back())){
                _back=dq.back();
                dq.pop_back();
                cuts.pop_back();
            }
            dq.push_back(_back);
        }
        dq.push_back(i);
        cuts.push_back(j);
    }
    void init(){
        dq.clear();
        cuts.clear();
    }
    long long get(long long x){
        this->remove(x);
        return dq.front().first*x+dq.front().second;
    }
    long long getcuts(){
        return cuts.front();
    }
} *hull=new linear_hull();
//so we know how many cuts is used when doing our linear convex hull

void lagrangian_multiplier(long long cost){
    hull->init();
    hull->add(ll(0,0),1);
    long long best;
    for (long long x=1;x<n;x++){
        best=hull->get(pre[x])+pre[x]*pre[x];
        hull->add(ll(-2*pre[x],best+pre[x]*pre[x]+cost),(hull->getcuts())+1);
    }
    val=hull->get(pre[n])+pre[n]*pre[n];
    groups=hull->getcuts();
}

int main(){
    scanf("%d%d",&n,&k);
    for (int x=1;x<=n;x++) scanf("%d",&arr[x]);
    for (int x=1;x<=n;x++) pre[x]=arr[x]+pre[x-1];
    long long a=0,b=(long long)200000000000005,c;
    while (a!=b){
        c=(a+b)>>1;
        lagrangian_multiplier(c);
        if (groups>k){
            a=c+1;
        }
        else if (groups<k){
            b=c;
        }
        else{
            ///we have found a optimal cost, c to spilt into k groups
            break;
        }
    }
    printf("%lld\n",val-(groups-1)*c); ///rmb to minus the extra cost in lagrange speedup to get the actual value
}