#include <iostream>
#include <vector>
#define inf 1'000'000'000'000'000'000
#define int long long
#define EPS 0.0000001
using namespace std;
struct ln
{
int m;
int c;
double p;
};
int a[100005];
int vs[100005];
int par[205][100005];
vector<int> dp(100005);
vector<int> ndp(100005);
vector<pair<ln, int>> cht;
double getx(int m1, int c1, int m2, int c2)
{
return (double)(c1-c2)/(m2-m1);
}
void vstavi(int m, int c, int ix)
{
double p = -inf;
while (!cht.empty())
{
p = getx(m, c, cht.back().first.m, cht.back().first.c);
if (p <= cht.back().first.p-EPS)
cht.pop_back();
else
break;
}
cht.push_back({ {m, c, p}, ix });
}
int getBestY(int x)
{
int k = 0;
int L = 0, R = cht.size()- 1;
while (L <= R)
{
int mid = (L+R) >> 1;
if (cht[mid].first.p <= x+EPS)
k = mid, L = mid+1;
else
R = mid-1;
}
// cout << cht[k].first.m << " " << cht[k].first.c << "\n";
return cht[k].second;
}
int32_t main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
vs[i] = vs[i-1]+a[i];
}
for (int i = 0; i <= k; i++)
{
cht.clear();
vstavi(0, 0, 0);
for (int j = 1; j <= n; j++)
{
int x = getBestY(vs[j]);
ndp[j] = dp[x] + (vs[j]-vs[x])*(vs[n]-vs[j]);
// if (i == 0)
// cout << j << " " << x << " " << ndp[j] << "\n";
par[i][j] = x;
vstavi(vs[j], dp[j]-vs[j]*vs[n], j);
}
dp = ndp;
}
// for (int i = 1; i <= n; i++)
// cout << dp[n] << "\n";
cout << dp[n] << "\n";
int tr = n;
for (int i = k; i > 0; i--)
{
tr = par[i][tr];
cout << tr << " ";
}
cout << "\n";
return 0;
}
