#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define pii pair<int, int>
using namespace std;
const int N = 5010;
int n,a[N],m;
ll d[N],sum[N],cost[N];
pair <ll,ll> line[N];
int sz;
long double x1,x2;

long double meet(pair <ll,ll> a, pair <ll,ll> b){
	return (a.s - b.s + 0.0) / (b.f - a.f);
}

void add(pair <ll,ll > p){
	int k = sz;
	while (k >= 2 && (line[k-1].f - line[k].f) * (line[k].s - p.s) >= (line[k].s - line[k-1].s) * (p.f - line[k].f)) k--;
	line[++k] = p;
	sz = k;
}

int main () {
	//freopen("out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i] = sum[i-1] + a[i];
		cost[i] = cost[i-1] + i * a[i];

	}
	for(int i=1;i<=n;i++){
		d[i] = cost[i];
		add(mp(-i,d[i] - cost[i] + sum[i] * ( i)));
	}
	int k;
	for(int j=2;j<=m;j++){
		k = 1;
		for(int i=j;i<=n;i++){
			while(k < sz){
				x1 = meet(line[k],line[k+1]);
				if(x1 >= sum[i]) break;
				k++;
			}
			d[i] = line[k].f * sum[i] + line[k].s + cost[i];
		}
		sz = 0;
		for(int i=j;i<=n;i++){
			add(mp(-i,d[i] - cost[i] + sum[i] * (i)));
		}
	}
	cout << d[n];

return 0;
}