#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long lld;
const static int MAXN = 1005;
const static int MAXK = 205;
int N, K, P[MAXN][MAXK];
lld S[MAXN], D[MAXN][MAXK];
void input(){
cin >> N >> K;
for (int i=1; i<=N; i++){
cin >> S[i];
S[i] += S[i-1];
}
}
int DP(){
memset(D, -1, sizeof(D));
for (int i=1; i<=N; i++) D[i][0] = 0;
for (int i=1; i<=N; i++){
for (int j=1; j<=min(K, i-1); j++){
int prev = -1;
for (int k=1; k<i; k++){
if (D[k][j-1] == -1) continue;
lld val = D[k][j-1] + S[k] * (S[i] - S[k]);
if (val > D[i][j]){
prev = k;
D[i][j] = val;
}
}
P[i][j] = prev;
}
}
return K;
}
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
input();
int j = DP();
cout << D[N][j] << endl;
vector<int> ans;
int i = N;
while (j > 0){
ans.push_back(P[i][j]);
i = P[i][j];
j -= 1;
}
reverse(ans.begin(), ans.end());
for (auto &i : ans) cout << i << ' ';
cout << endl;
}
