#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e18

int pf[100001];

map<tuple<int,int,int>,int>mem;

int cost(int s,int e){
	return (pf[e]-pf[s])*(e-s);
}

int solve(int s,int e,int k){
	if(k==0){
		return cost(s,e);
	}
	if(mem.find({s,e,k})!=mem.end()){
		return mem[{s,e,k}];
	}
	int k1,k2;
	if(k==1){
		k1=0;
		k2=0;
	}
	else{
		k1=k-2;
		k2=1;
	}
	auto calc=[&](int i)->int{
		return solve(s,i,k1)+solve(i,e,k2);
	};
	int l=s+k1+1,h=e-k2-1;
	while(h-l>=3){
		int m1=l+(h-l)/3;
		int m2=h-(h-l)/3;
		if(calc(m1)<=calc(m2)){
			h=m2;
		}
		else{
			l=m1;
		}
	}
	int res=INF;
	for(int i=l;i<=h;i++){
		res=min(res,calc(i));
	}
	mem[{s,e,k}]=res;
	return res;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N);
	for(int i=0;i<N;i++){
		cin>>v[i];
	}
	for(int i=0;i<N;i++){
		pf[i+1]=pf[i]+v[i];
	}
	cout<<solve(0,N,K)<<'\n';
	// cout<<K<<" "<<mem.size()<<'\n';
	return 0;
}