#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define MIN(x,y) ((x) > (y) ? (y) : (x))
using namespace std;
const int maxn=100000+10;
int n,k,size,temp,leave[maxn];
pair<long long,long long> s[maxn];
long long dp[maxn][11],sum[maxn];

void addline(long long a,long long b)
{
        while (size>=2&& (s[size-1].second-b)/(a-s[size-1].first)>=(s[size-1].second-s[size].second)/(s[size].first-s[size-1].first) ) size--;
        size++;
        s[size].first=a;
        s[size].second=b;
}
long long query(int x)
{
  long long best=x*s[temp].first+s[temp].second;
  int i=temp+1;
  while (i<=size){
    if (x*s[i].first+s[i].second>best) {
          best=x*s[i].first+s[i].second;
          temp=i;
      } else break;
      i++;
  }
  return best;
}


int main()
{
    long long res=0;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d %d",&n,&k);
    FOR(i,1,n) scanf("%d",&leave[i]);
    RFOR(i,n,1){
      sum[i]=sum[i+1]+leave[i];
      res=res+sum[i];
    }
    temp=1;
    FOR(j,2,k){
      size=0;
      int tg=n-j+2;
      addline( -sum[tg],dp[tg][j-1]+tg*sum[tg]);
      temp=1;
      RFOR(i,n-j+1,1){
        dp[i][j]=query(i);
       addline(-sum[i],dp[i][j-1]+i*sum[i]);
       temp=MIN(temp,size);
      }
    }
    cout << res-sum[1]-dp[1][k];

    return 0;
}