#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n,k,i,j,q;
cin>>n>>k;
vector<ll> a(n+1);
vector<ll> pre(n+2,0);
for(i=1 ; i<=n ; i++) cin>>a[i];
for(i=1 ; i<=n ; i++) pre[i]=pre[i-1]+a[i];
vector<vector<ll>> dp(k+1,vector<ll>(n+1,0));
vector<vector<ll>> par(k+1,vector<ll>(n+1));
vector<ll> path;
for(i=1 ; i<=k ; i++){
for(j=1 ; j<=n ; j++){
for(q=1 ; q<j ; q++){
ll val=dp[i-1][q]+pre[q]*(pre[j]-pre[q]);
if(val>=dp[i][j]){
dp[i][j]=val;
par[i][j]=q;
}
}
}
}
ll u=n;
for(i=k ; i>=1 ; i--){
path.push_back(par[i][u]);
u=par[i][u];
}
cout<<dp[k][n]<<"\n";
for(auto v:path) cout<<v<<" ";
return 0;
}
