/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <cassert>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n, k;
LL a[100005], pr[100005], dp[2][100005];
int nxt[202][100005];
LL sum(int l, int r)
{
return pr[r] - pr[l - 1];
}
struct line
{
int i;
LL k, b;
line(LL kk = 0, LL bb = 0, int ii = 0)
{
k = kk;
b = bb;
i = ii;
}
};
LL f(line g, LL x)
{
return g.k*x + g.b;
}
line maxLine(line a,line b,LL x)
{
if (a.k*x + a.b >= b.k*x + b.b)
return a;
return b;
}
vector<line> t;
vector<int> lson, rson;
void update(int v,LL l,LL r,line nw)
{
LL m = (l + r) / 2;
bool lef = f(t[v], l) < f(nw, l);
bool mid = f(t[v], m) < f(nw, m);
if (mid)
swap(nw, t[v]);
if (r - l == 0)
return;
else if (lef != mid)
{
if (lson[v] == -1)
{
lson[v] = t.size();
t.PB(line(0,-mod*mod));
lson.PB(-1);
rson.PB(-1);
}
update(lson[v],l,m,nw);
}
else
{
if (rson[v] == -1)
{
rson[v] = t.size();
t.PB(line(0, -mod * mod));
lson.PB(-1);
rson.PB(-1);
}
update(rson[v], m+1, r, nw);
}
}
line get(int v,LL l,LL r,LL x)
{
if (l == r)
return t[v];
LL m = (l + r) / 2;
if (x <= m)
{
if (lson[v] == -1)
{
lson[v] = t.size();
t.PB(line(0, -mod * mod));
lson.PB(-1);
rson.PB(-1);
}
return maxLine(t[v], get(lson[v],l,m,x),x);
}
else
{
if (rson[v] == -1)
{
rson[v] = t.size();
t.PB(line(0, -mod * mod));
lson.PB(-1);
rson.PB(-1);
}
return maxLine(t[v], get(rson[v], m + 1, r, x), x);
}
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pr[i] = pr[i - 1] + a[i];
}
for (int z = 1; z <= k; z++)
{
int i = z % 2;
int l = !i;
t.resize(0);
lson.resize(0);
rson.resize(0);
t.PB(line(0,-mod*mod));
lson.PB(-1);
rson.PB(-1);
for (int j = n; j >= 1; j--)
{
line add = line(pr[j], dp[l][j + 1] - pr[j] * pr[j], j);
update(0,0,2*mod,add);
LL X = pr[n] + pr[j - 1];
line best = get(0,0,2*mod,X);
dp[i][j] = best.k*X + best.b - pr[j - 1] * pr[n];
nxt[z][j] = best.i;
}
}
cout << dp[k % 2][1] << endl;
for (int i = k, l = 1; i >= 1; i--)
{
cout << nxt[i][l] << " ";
l = nxt[i][l] + 1;
}
cout << endl;
return 0;
}
/*
3 1
2 1 2
40 3
7 5 7 5 1 2 3 4 6 7 8 2 1 2 3 4 6 7 8 2 7 7 5 1 2 3 4 6 7 8 2 5 1 2 3 4 6 7 8 2
7 3
4 1 3 4 0 2 3
*/
