#include<bits/stdc++.h>
#define P pair<lli, lli>
#define x first
#define y second
#define mp make_pair
using namespace std;
typedef long long int lli;
const lli N=10009, K=209;
lli n, k, a[N], s[N], low[4*N], high[4*N], f[N][K], trace[N][K], leaf[N], maxnode=0;
struct T
{
lli a, b, id;
};
struct T1
{
lli x, a, b, id;
};
deque<T1> p;
T node[4*N];
void Built(lli v, lli l, lli h)
{
maxnode=max(maxnode, v);
low[v]=l;
high[v]=h;
if(l==h)
{
leaf[l]=v;
}
else
{
lli m=(l+h)/2;
Built(v*2, l, m);
Built(v*2+1, m+1, h);
}
}
void Inp()
{
cin>>n>>k;
k++;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
Built(1, 1, n);
}
lli Get(T p, lli k)
{
return p.a*k+p.b;
}
void Update(lli v, lli l, lli h, T val)
{
if(l>h)
{
return ;
}
if(low[v]>h||high[v]<l)
{
return ;
}
if(low[v]>=l&&high[v]<=h)
{
if(Get(node[v], s[low[v]])>=Get(val, s[low[v]])&&Get(node[v], s[high[v]])>=Get(val, s[high[v]]))
{
return ;
}
if(Get(node[v], s[low[v]])<=Get(val, s[low[v]])&&Get(node[v], s[high[v]])<=Get(val, s[high[v]]))
{
node[v]=val;
return ;
}
lli m=(low[v]+high[v])/2;
if(Get(node[v], s[low[v]])>=Get(val, s[low[v]])&&Get(node[v], s[m])>=Get(val, s[m]))
{
Update(v*2+1, l, h, val);
return ;
}
if(Get(node[v], s[low[v]])<=Get(val, s[low[v]])&&Get(node[v], s[m])<=Get(val, s[m]))
{
Update(v*2+1, l, h, node[v]);
node[v]=val;
return ;
}
if(Get(node[v], s[m+1])>=Get(val, s[m+1])&&Get(node[v], s[high[v]])>=Get(val, s[high[v]]))
{
Update(v*2, l, h, val);
return ;
}
Update(v*2, l, h, node[v]);
node[v]=val;
return ;
}
Update(v*2, l, h, val);
Update(v*2+1, l, h, val);
}
void Pre()
{
for(int i=1;i<=maxnode;i++)
{
node[i]={0, 0, 0};
}
while(!p.empty())
{
T1 v=p.front();
p.pop_front();
Update(1, v.x, n, {v.a, v.b, v.id});
}
}
P Max(lli k)
{
lli v=leaf[k], maxx=-1, id;
while(v)
{
if(maxx<Get(node[v], s[k]))
{
maxx=Get(node[v], s[k]);
id=node[v].id;
}
v=v/2;
}
return mp(maxx, id);
}
void Solve()
{
for(int i=1;i<=n;i++)
{
f[i][1]=0;
p.push_back({i+1, s[i], -s[i]*s[i]+f[i][1], i});
}
for(int j=2;j<=k;j++)
{
Pre();
for(int i=j;i<=n;i++)
{
P ans=Max(i);
f[i][j]=ans.x;
trace[i][j]=ans.y;
p.push_back({i+1, s[i], -s[i]*s[i]+f[i][j], i});
}
}
cout<<f[n][k]<<endl;
lli x=n;
for(int i=k;i>=2;i--)
{
cout<<trace[x][i]<<" ";
x=trace[x][i];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
Inp();
Solve();
}
