#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define N 10010
#define ii pair<ll,int>
#define fs first
#define sc second
#define ld double
#define int ll
void selfmax(int&u,int v)
{
u=max(u,v);
}
int dp[N][210],n,k,sum[N];
void solve(int l,int r,int best_l,int best_r,int t)
{
int res=-1e18,mid=(l+r)/2,vt=0;
for(int i=best_l;i<min(best_r+1,mid);i++)
if(dp[i][t-1]+sum[i]*(sum[mid]-sum[i])>res)
{
res=dp[i][t-1]+sum[i]*(sum[mid]-sum[i]);
vt=i;
}
//cout<<l<<" "<<r<<" "<<best_l<<" "<<best_r<<" "<<mid<<" "<<res<<endl;
dp[mid][t]=res;
if(l<mid)
solve(l,mid-1,best_l,vt,t);
if(mid<r)
solve(mid+1,r,vt,best_r,t);
}
int32_t main()
{
#ifdef SKY
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
#endif // SKY
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>sum[i],sum[i]+=sum[i-1];
memset(dp,-0x3f3f,sizeof(dp));
for(int i=1;i<=n;i++)
dp[i][0]=0;
for(int t=1;t<=k;t++)
solve(t+1,n,t,n,t);
cout<<dp[n][k]<<endl;
int vt=n;
for(int t=k;t>=1;t--)
{
for(int i=t;i<vt;i++)
if(dp[i][t-1]+sum[i]*(sum[vt]-sum[i])==dp[vt][t])
{
cout<<i<<" ";
vt=i;
break;
}
}
}
