//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const long long N = 2000+7;
long long a[N];
long long pref[N];
//long long suf[N];
pair<long long,long long> check(long long l,long long r){
long long ans = 0;
long long pos = l;
for(long long i = l;i<=r-1;i++){
long long x = pref[i]-pref[l-1];
long long y = pref[r]-pref[i];
x*=y;
if(x>ans){
ans = x; pos = i;
}
}
return make_pair(ans,pos);
}
pair<long long,long long> dp[N][N];
long long par[N][N];
int main()
{
long long n,k;
cin>>n>>k;
for(long long i = 1;i<=n;i++) cin>>a[i];
for(long long i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
// for(long long i = n;i>=1;i--) suf[i] = suf[i+1]+a[i];
for(long long i = 1;i<=n;i++){
dp[1][i] = check(1,i);
}
for(long long kk = 2;kk<=k;kk++){
for(long long i = 1;i<=n;i++){
for(long long j = 1;j<i;j++){
if(dp[kk-1][j].first+(pref[i]-pref[j])*pref[j]>dp[kk][i].first){
dp[kk][i].first = dp[kk-1][j].first+(pref[i]-pref[j])*pref[j];
dp[kk][i].second = j;
}
}
}
}
cout<<dp[k][n].first<<endl;
long long kk = k;
long long nn = n;
while(dp[kk][nn].second!=0){
cout<<dp[kk][nn].second<<" ";
nn = dp[kk][nn].second;
kk--;
}
cout<<endl;
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
