#include <bits/stdc++.h>
using namespace std;
#define MAX 100100
#define MAXK 202
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))
template<class X,class Y> bool maximize(X &x,Y y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class X,class Y> bool minimize(X &x,Y y)
{
if(y<x)
{
x=y;
return 1;
}
return 0;
}
const int inf=1e9+412009;
const ll INF=2e18+412009;
int n,K;
int a[MAX];
void nhap()
{
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i];
}
ll dp[MAX][2]={};
int trace[MAX][MAXK]={};
ll f[MAX];
void solve()
{
for(int i=1;i<=n;i++) f[i]=f[i-1]+a[i];
for(int i=1;i<=n;i++) dp[i][1]=f[i]*(f[n]-f[i]);
for(int k=2;k<=K;k++)
{
for(int i=1;i<=n;i++) dp[i][0]=dp[i][1],dp[i][1]=0;
for(int i=k;i<=n;i++) for(int j=i;j>=k-1;j--)
{
if(maximize(dp[i][1],dp[j-1][0]+(f[i]-f[j-1])*(f[n]-f[i])))
{
trace[i][k]=j-1;
}
}
}
ll ans=0;
int u=0;
for(int i=1;i<=n;i++)
{
if(maximize(ans,dp[i][1])) u=i;
}
cout<<ans<<'\n';
stack<int> tracing;
int v=K;
while(v!=0)
{
tracing.push(u);
u=trace[u][v];
v--;
}
while(!tracing.empty()) cout<<tracing.top()<<' ',tracing.pop();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
// freopen("SPLIT_THE_SEQUENCE_APIO14.INP","r",stdin);
// freopen("SPLIT_THE_SEQUENCE_APIO14.OUT","w",stdout);
nhap();
solve();
return 0;
}
