#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
using namespace std;
const int maxn = 53;
struct CTDL{
int pos = 0,k1 = 0,k2 = 0;
};
ll dp[maxn][maxn][maxn],sum[maxn];
CTDL trace[maxn][maxn][maxn];
inline ll S(int l,int r){
return sum[r] - sum[l - 1];
}
int a[maxn];
void getdp(int l,int r,int k){
for (int i = l ; i < r ; i++)
for (int k1 = 0 ; k1 < k ; k1++)
for (int k2 = 0 ; k2 + k1 < k ; k2++){
ll T = dp[l][r][k1 + k2 + 1];
ll tmp = dp[l][i][k1] + dp[i + 1][r][k2] + S(l,i)*S(i + 1,r);
if (T < tmp){
dp[l][r][k1 + k2 + 1] = tmp;
trace[l][r][k1 + k2 + 1] = {i,k1,k2};
}
}
}
void Trace_back(int l,int r,int k){
if (!k) return;
CTDL t = trace[l][r][k];
cout << t.pos << " ";
Trace_back(l,t.pos,t.k1);
Trace_back(t.pos + 1,r,t.k2);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
int n,k;
cin >> n >> k;
for (int i = 1 ; i <= n ; i++){
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for (int len = 1 ; len <= n ; len++)
for (int i = 1 ; i <= n - len + 1 ; i++)
getdp(i,i + len - 1,k);
cout << dp[1][n][k] << "\n";
Trace_back(1,n,k);
return 0;
}
