#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
#define fi first
#define se second
const int MAXN = 1e3+5;
const int MAXK = 205;
// f(x,y) = score
// x = pemotongan ke-x
// y = indeks pemotongan
//
//
int N, K;
int data[MAXN], pref[MAXN], suff[MAXN];
int dp[MAXK][MAXN], ans=0;
int tambah[MAXK][MAXN];
stack<int>putus;
void cariSkenario(int cnt, int str, int score){
if(cnt == 0) return;
for(;str>0;str--){
if(dp[cnt][str] == score){
putus.push(str);
cariSkenario(cnt-1, str-1, score-tambah[cnt][str]);
break;
}
}
}
void DFS(int pos){
if(pos == 1) return;
putus.push(tambah[pos][putus.top()]);
DFS(pos-1);
}
int main(){
memset(data, 0, MAXN);
memset(pref, 0, MAXN);
memset(suff, 0, MAXN);
memset(dp, -1, sizeof dp);
for(int i=0;i<MAXN;i++) dp[0][i] = 0;
for(int i=0;i<MAXK;i++) dp[i][0] = 0;
cin >> N >> K;
for(int i=1;i<=N;i++){
cin >> data[i];
pref[i] = data[i]+pref[i-1];
}
for(int i=N;i>0;i--){
suff[i] = suff[i+1]+data[i];
}
for(int i=1; i<=K; i++){
for(int j=1;j<N;j++){
if(j < i) continue;
for(int l=0;l<j;l++){
int tmp = dp[i-1][l]+(pref[j]-pref[l])*suff[j+1];
if(dp[i][j] <= tmp){
dp[i][j] = tmp;
tambah[i][j] = l;
}
}
}
}
for(int i=1;i<N;i++) ans = max(ans, dp[K][i]);
for(int i=N-1;i>0;i--){
if(ans == dp[K][i]){
putus.push(i);
break;
}
}
DFS(K);
cout << ans << endl;
cout << putus.top();
putus.pop();
while(!putus.empty()){
cout << " " << putus.top();
putus.pop();
}
cout << endl;
}
