#include <stdio.h>
#include <stdlib.h>
typedef struct solution
{
int lastcut;
int ncuts;
int cuts[200];
long long value;
} solution;
int k;
int compar(const void* p1, const void* p2)
{
solution * m1 = (solution *)p1;
solution * m2 = (solution *)p2;
int c = m1->ncuts - m2->ncuts;
int p = m1-> lastcut - m2->lastcut;
long long v = m2->value - m1->value;
if (c==0)
{
if (p==0 || m1->ncuts==k)
{
if (v>0) return 1;
if (v<0) return -1;
return 0;
}
return p;
}
return c;
}
int tamanho[201];
solution **s;
void tam(int vv)
{
tamanho[vv] *= 2;
s[vv] = (solution*) realloc(s[vv],tamanho[vv]*sizeof(solution));
}
void copysol(int vv, int to, int from)
{
s[vv][to].lastcut = s[vv][from].lastcut;
s[vv][to].ncuts = s[vv][from].ncuts;
s[vv][to].value = s[vv][from].value;
int i;
for (i=0;i<s[vv][to].ncuts;i++)
s[vv][to].cuts[i] = s[vv][from].cuts[i];
}
int main()
{
int n,i,j,jj,jjj,p;
long long * a;
long long * b;
scanf("%d", &n);
scanf("%d", &k);
a = (long long *) malloc(n*sizeof (long long));
for (i=0;i<n;i++) scanf("%lld",&a[i]);
b = (long long *) malloc(n * sizeof(long long));
b[n-1]=a[n-1];
for (i=n-2;i>=0;i--) b[i] = b[i+1]+a[i];
//b[i] guarda a soma de i ate o fim
s = (solution**) malloc ((k+1)*sizeof(solution*));
for (i=0;i<=k;i++)
{
s[i] = 0;
tamanho[i] = 200;
tam(i);
}
int nsols[201];
nsols[0]=1;
for(i=1;i<=k;i++) nsols[i]=0;
s[0][0].lastcut = 0;
s[0][0].value = 0;
s[0][0].ncuts = 0;
int ss;
for (i=0;i<n-1;i++)
{
//tentar cortar entre i e i+1
for (jjj=k-1;jjj>=0;jjj--) //tamanho do ncuts anterior
{
ss = nsols[jjj];
if (ss==0) continue;
for (j=0;j<ss;j++)
{
//if (s[j].ncuts==k) continue; //nao posso mais cortar
s[jjj + 1][nsols[jjj + 1]].lastcut = i+1;
s[jjj + 1][nsols[jjj + 1]].ncuts = s[jjj][j].ncuts+1;
s[jjj + 1][nsols[jjj + 1]].value = s[jjj][j].value + b[i+1]*(b[s[jjj][j].lastcut] - b[i+1]);
for (jj=0;jj<s[jjj][j].ncuts;jj++) s[jjj+1][nsols[jjj+1]].cuts[jj] = s[jjj][j].cuts[jj];
s[jjj + 1][nsols[jjj + 1]].cuts[jj] = i+1;
nsols[jjj + 1]++; if (nsols[jjj + 1]==tamanho[jjj + 1]) tam(jjj + 1);
}
//aqui seria uma boa hora para descartar solucoes.
qsort(s[jjj+1], nsols[jjj+1], sizeof(solution), compar);
/*
for (j = 0; j<nsols; j++)
{
printf("sol %d: %d %d %lld\n", j, s[j].ncuts, s[j].lastcut, s[j].value);
}
printf("\n");
*/
j=0;
p=0;
do
{
copysol(jjj+1,j,p);
p++;
//while( p<nsols && s[p].ncuts == s[j].ncuts && s[p].value <= s[j].value ) p++;
while (p<nsols[jjj+1] && s[jjj+1][p].value <= s[jjj+1][j].value) p++;
j++;
} while(p<nsols[jjj+1]); // && s[p].ncuts!=k);
/*
if (p<nsols)
{
copysol(j,p);
j++;
}
*/ //essa parte nao precisa mais porque cada um eh seu vetor e k foi tratado igual
nsols[jjj+1]=j;
}
}
//nao guardei dados o suficiente pra imprimir a repsosta,
//mas vamos ver se pelo menos o valor total sai certo.
/*
for(j=0;j<nsols;j++)
{
printf("sol %d: %d %d %lld - %d %d %d\n",j,s[j].ncuts,s[j].lastcut,s[j].value,
s[j].cuts[0], s[j].cuts[1], s[j].cuts[2]);
}*/
//procurar a atual maior valor solucao e imprimir
qsort(s[k], nsols[k], sizeof(solution), compar);
//vai ser a ultima que eh a unica com k cuts
//printf("%lld\n",s[nsols-1].value);
printf("%lld\n", s[k][0].value);
for (i=0;i<k;i++) printf("%d ",s[k][0].cuts[i]);
printf("\n");
}
