#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42,kmax=2e2+5;
long long dp[2][nmax];
int optimal[kmax][nmax];
int n,k;
int inp[nmax];
long long pref[nmax];
long long ask(int l,int r)
{
return pref[r]-pref[l-1];
}
long long score(int j,int i)
{
return ask(1,j)*ask(j+1,i);
}
int output[nmax];
int brute(int cuts,int i,int lq,int rq)
{
int ret=-1;
dp[cuts&1][i]=-1;
for(int j=lq;j<=rq&&j<i;j++)
{
long long current=dp[(cuts-1)&1][j]+score(j,i);
if(current>dp[cuts&1][i])
{
ret=j;
dp[cuts&1][i]=current;
}
}
//cout<<"brute "<<cuts<<" "<<i<<" "<<lq<<" "<<rq<<" -> "<<ret<<endl;
return ret;
}
void dc(int cuts,int l,int r,int lq,int rq)
{
if(l>r)return;
rq=min(r,rq);
int av=(l+r)/2;
optimal[cuts][av]=brute(cuts,av,lq,rq);
dc(cuts,l,av-1,lq,optimal[cuts][av]);
dc(cuts,av+1,r,optimal[cuts][av],rq);
}
int main()
{
scanf("%i%i",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%i",&inp[i]);
pref[i]=pref[i-1]+inp[i];
}
for(int cuts=1;cuts<=k;cuts++)
{
for(int j=0;j<=n;j++)
dp[cuts%2][j]=-1e18;
dc(cuts,cuts+1,n,1,n);
//for(int j=1;j<=n;j++)cout<<optimal[cuts][j]<<" ";cout<<endl;
}
printf("%lld\n",dp[k%2][n]);
int pos=n;
for(int cuts=k;cuts>=1;cuts--)
{
output[cuts]=optimal[cuts][pos];
pos=optimal[cuts][pos];
}
for(int i=1;i<=k;i++)
{
printf("%i",output[i]);
if(i==k)printf("\n");
else printf(" ");
}
return 0;
}
