#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//#define getchar() getchar_unlocked()
using namespace std;
ll n,k,i,a[101010],p[101010],M,C,opt,j,vs;
ll d[2][100010],te,seb;
int op[201][100010],poi;
int v[202];
pair<pair<ll,ll> ,int> vt[101010];
pair<pair<ll,ll> ,int> L1,L2,L3;
bool bo;
void bt(ll aa,ll bb)
{
ll ii,h=0;
for(ii=0;ii<k;ii++)
{
v[h]=op[aa][bb];
h++;
bb=op[aa][bb]+1;
aa--;
}
}
inline void fs(ll& p) {
static char c;
while ((c = getchar()) < '0');
for (p = c-'0'; (c = getchar()) >= '0'; p = p*10+c-'0');
}
int main()
{
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//cin>>n>>k;
fs(n);
fs(k);
for(i=1;i<=n;i++)
{
fs(a[i]);
// cin>>a[i];
p[i]=p[i-1]+a[i];
}
pair<pair<ll,ll>,ll> aa;
ll ava;
for(i=1;i<=k;i++)
{
// vt.clear();
// vt.reserve(n);
poi=0;
vs=0;
te=0;
seb=0;
for(j=n-1;j>=1;j--)
{
M=p[j];
C=p[j]*p[n]-p[j]*p[j]+d[(i-1)&1][j+1];
aa=mp(mp(M,C),j);
bo=0;
while(vs>=2)
{
L1=vt[vs-1];
L2=vt[vs-2];
L3=aa;
if((L2.fi.se-L1.fi.se)*(L2.fi.fi-L3.fi.fi)<(L3.fi.se-L2.fi.se)*(L1.fi.fi-L2.fi.fi))
break;
// if(!bo&&L2.se>seb){te--;bo=1;}
poi--;
//vt.pop_back();
vs--;
}
vt[poi]=aa;
poi++;
//vt.push_back(aa);
vs++;
ava=p[j-1];
if(te==-1)
te=0;
while(te<vs-1)
{
L1=vt[te];
L2=vt[te+1];
if((L2.fi.se-L1.fi.se)>=(L1.fi.fi-L2.fi.fi)*ava)
te++;
else
break;
}
seb=vt[te].se;
opt=te;
te--;
op[i][j]=vt[opt].se;
d[i&1][j]=(vt[opt].fi.fi*p[j-1]+vt[opt].fi.se-p[j-1]*p[n]);
}
}
cout<<d[k%2][1]<<"\n";
bt(k,1);
for(i=0;i<k;i++)
if(i==k-1)
cout<<v[i]<<"\n";
else
cout<<v[i]<<" ";
}
