cbarn2.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e2 + 5;
const ll INF = 1e12;

int v[maxn];
ll dp[2*maxn][2*maxn][10];

ll solve(int l, int r, int k){
	if(l>r) return 0;
	if(k==-1) return INF;
	if(l==r) return 0;
	if(dp[l][r][k]!=-1) return dp[l][r][k];

	ll rt = INF, cont = 0;
	for(int i = l; i <= r; i++){
		cont += (i-l)*v[i];
		rt = min(rt, cont+solve(i+1, r, k-1));
	}
	return dp[l][r][k] = rt;
}

int main(){
	freopen("cbarn2.in", "r", stdin);
	freopen("cbarn2.out", "w", stdout);

	int n, k; cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> v[i];
		v[i+n] = v[i];
	}

	memset(dp, -1, sizeof dp);
	ll ans = INF;
	for(int i = 0; i < n; i++){
		ans = min(ans, solve(i, i+n-1, k-1));
	}

	cout << ans << '\n';
}