#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int kx=2e2+5, nx=1e5+5;
int n, k;
ll dp[kx][nx], qs[nx];
int bk[kx][nx];
void solve(int l, int r, int optl, int optr, int layer)
{
if (l>r) return;
int md=(l+r)/2, c=layer%2, pv=1-c;
pair<ll, ll> p={LLONG_MAX, 0};
for (int i=optl; i<=min(optr, md-1); i++) if (dp[pv][i]!=LLONG_MAX) p=min(p, {dp[pv][i]+(qs[md]-qs[i])*(qs[md]-qs[i]), i});
dp[c][md]=p.first;
bk[layer][md]=p.second;
solve(l, md-1, optl, p.second, layer);
solve(md+1, r, p.second, optr, layer);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>qs[i], qs[i]+=qs[i-1];
for (int i=0; i<2; i++) for (int j=0; j<nx; j++) dp[i][j]=LLONG_MAX;
dp[0][0]=0;
for (int i=1; i<=k+1; i++)
{
for (int j=0; j<nx; j++) dp[i%2][j]=LLONG_MAX;
solve(1, n, 0, n, i);
}
cout<<(qs[n]*qs[n]-dp[(k+1)%2][n])/2<<'\n';
ll l=n, ly=k+1;
while (ly>1)
{
l=bk[ly][l];
ly--;
cout<<l<<' ';
}
}
