#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
struct LINE
{
long long m,c;
int idx;
};
int n,k,back[100010][205];
int qs[100010];
vector<LINE> stk;
queue<LINE> q[2];
int poi;
long long get_y(LINE p,long long x)
{
return p.m*x+p.c;
}
long long chk(LINE a,LINE b,LINE c) // if positive xa > xb
{
return (c.c-a.c)*(b.m-c.m) - (c.c-b.c)*(a.m-c.m);
}
void push(LINE p)
{
while(stk.size()>=2 && chk(stk[stk.size()-2],stk[stk.size()-1],p)>0)
{
stk.pop_back();
//printf("pop hap\n");
}
while(stk.size()>=1 && stk[stk.size()-1].m==p.m && stk[stk.size()-1].c<=p.c)
{
//printf("pop: %d %d\n",stk[cnt][stk[cnt].size()-1],p.c);
stk.pop_back();
//printf("pop hap\n");
}
stk.push_back(p);
}
pair<long long,int> query(long long x)
{
if(poi>=stk.size())
poi=stk.size()-1;
//printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
//printf("%d %d %d\n",poi[cnt],stk[cnt][poi[cnt]].idx,idx);
while(poi+1<stk.size() && get_y(stk[poi],x)<=get_y(stk[poi+1],x))
poi++;
//printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
return {get_y(stk[poi],x),stk[poi].idx};
}
long long qsl(int l,int r)
{
return qs[r]-qs[l-1];
}
main()
{
qs[0]=0;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&qs[i]);
qs[i]=qs[i]+qs[i-1];
}
long long ans=0;
int bb=-1;
// for(int i=1;i<n;i++)
// {
// //printf("-----%d-----\n",i);
// for(int j=min(i,k);j>=2;j--)
// {
// }
// }
LINE temp;
for(int i=1;i<n;i++)
{
long long dp=qsl(1,i)*qsl(i+1,n);
back[i][1]=0;
//printf("1 %lld %d\n",dp[i][1],back[i][1]);
temp.m=(long long)qs[i];
temp.c=dp-(long long)qs[i]*(long long)qs[n];
temp.idx=i;
//printf("push: %lld %lld\n",temp.m,temp.c);
q[1%2].push(temp);
if(1==k&&ans<=dp)
{
ans=dp;
bb=i;
}
}
for(int j=2;j<=k;j++)
{
poi=0;
for(int i=j;i<n;i++)
{
push(q[(j+1)%2].front());
q[(j+1)%2].pop();
pair<long long,int> ret=query(qs[i]);
long long dp=ret.F+(long long)qs[i]*((long long)qs[n]-(long long)qs[i]);
back[i][j]=ret.S;
//printf("%d %lld %d\n",j,dp[i][j],back[i][j]);
temp.m=qs[i];
temp.c=dp-(long long)qs[i]*(long long)qs[n];
temp.idx=i;
//printf("push: %lld %lld\n",temp.m,temp.c);
q[j%2].push(temp);
if(j==k&&ans<=dp)
{
ans=dp;
bb=i;
}
}
q[(j+1)%2].pop();
stk.clear();
}
int nw=k;
printf("%lld\n",ans);
while(bb)
{
printf("%d ",bb);
bb=back[bb][k--];
}
}
