#include <bits/stdc++.h>
using namespace std;
typedef pair<double,double> 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];
double val;
long long 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();
    }
    double 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(double cost){
    hull->init();
    hull->add(ll(0,0),0);
    double 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() + 1;
}

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];
    double a = 0, b = 2e9, c = -1;
    for (int it = 0; it < 400; ++it) {
      c = 0.5 * (a + b);
      lagrangian_multiplier(c);
      if (groups > k) {
        a = c;
      } else {
        b = c;
      }
    }
    lagrangian_multiplier((a + b) * 0.5);
    cout << (long long)round(val - (k - 1) * (a + b) * 0.5) << endl;  ///rmb to minus the extra cost in lagrange speedup to get the actual value
}