#include <stdio.h>
int N, K, Path[202][100002], S[100002], Top, Ans[202];
long long A[100002], D[2][100002];
void input(void)
{
int i;
scanf("%d %d",&N,&K);
for(i=1 ; i<=N ; i++)
{
scanf("%lld",&A[i]);
A[i]+=A[i-1];
}
}
void process(void)
{
int i, j, k, x, now;
long long a, b, c, d, e, f;
for(j=1 ; j<=K ; j++)
{
x=j%2;
Top=0;
now=1;
for(k=j ; k<=N ; k++)
{
if(Top<2)
S[++Top]=k;
else
{
a=A[S[Top-1]];
b=D[1-x][S[Top-1]]-A[S[Top-1]]*A[S[Top-1]];
c=A[S[Top]];
d=D[1-x][S[Top]]-A[S[Top]]*A[S[Top]];
e=A[k];
f=D[1-x][k]-A[k]*A[k];
while(Top>=2 && (d-b)*(e-a)<=(c-a)*(f-b))
{
Top--;
a=A[S[Top-1]];
b=D[1-x][S[Top-1]]-A[S[Top-1]]*A[S[Top-1]];
c=A[S[Top]];
d=D[1-x][S[Top]]-A[S[Top]]*A[S[Top]];
}
S[++Top]=k;
}
a=A[S[now]]*A[k+1]+D[1-x][S[now]]-A[S[now]]*A[S[now]];
b=A[S[now+1]]*A[k+1]+D[1-x][S[now+1]]-A[S[now+1]]*A[S[now+1]];
while(now<k && a<b)
{
now++;
a=A[S[now]]*A[k+1]+D[1-x][S[now]]-A[S[now]]*A[S[now]];
b=A[S[now+1]]*A[k+1]+D[1-x][S[now+1]]-A[S[now+1]]*A[S[now+1]];
}
D[x][k+1]=a;
Path[j][k+1]=S[now];
}
}
a=N;
for(i=K ; i>=1 ; i--)
{
Ans[i]=Path[i][a];
a=Path[i][a];
}
}
void output(void)
{
int i;
printf("%lld\n",D[K%2][N]);
for(i=1 ; i<=K ; i++)
printf("%d ",Ans[i]);
}
int main(void)
{
input();
process();
output();
return 0;
}
