#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];
//long long dp[100010][205];
vector<LINE> stk[205];
int poi[205];
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,int cnt)
{
while(stk[cnt].size()>=2 && chk(stk[cnt][stk[cnt].size()-2],stk[cnt][stk[cnt].size()-1],p)>0)
{
stk[cnt].pop_back();
//printf("pop hap\n");
}
while(stk[cnt].size()>=1 && stk[cnt][stk[cnt].size()-1].m==p.m && stk[cnt][stk[cnt].size()-1].c<=p.c)
{
//printf("pop: %d %d\n",stk[cnt][stk[cnt].size()-1],p.c);
stk[cnt].pop_back();
//printf("pop hap\n");
}
stk[cnt].push_back(p);
}
pair<long long,int> query(long long x,int cnt)
{
if(poi[cnt]>=stk[cnt].size())
poi[cnt]=stk[cnt].size()-1;
//printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
while(poi[cnt]+1<stk[cnt].size() && get_y(stk[cnt][poi[cnt]],x)<=get_y(stk[cnt][poi[cnt]+1],x))
poi[cnt]++;
//printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
return {get_y(stk[cnt][poi[cnt]],x),stk[cnt][poi[cnt]].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);
LINE temp;
for(int j=min(i,k);j>=2;j--)
{
pair<long long,int> ret=query(qs[i],j-1);
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);
push(temp,j);
if(j==k&&ans<dp)
{
ans=dp;
bb=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);
push(temp,1);
if(1==k&&ans<dp)
{
ans=dp;
bb=i;
}
}
int nw=k;
printf("%lld\n",ans);
while(bb)
{
printf("%d ",bb);
bb=back[bb][k--];
}
}
