//Smaug never desolated!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 3;
const int MAXS = (int)203;
const int MOD = (int)1e9 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e15;
bool Q;
struct Line
{
mutable ll k, m, p, id;
bool operator<(const Line& o) const
{
return Q ? p < o.p : k < o.k;
}
};
struct CHT : multiset<Line>
{
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b)
{
// floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y)
{
if (y == end())
{
x->p = inf;
return false;
}
if (x->k == y->k)
x->p = x->m > y->m ? inf : -inf;
else
x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m, ll id)
{
auto z = insert({k, m, 0, id}), y = z++, x = y;
while (isect(y, z))
z = erase(z);
if (x != begin() && isect(--x, y))
isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x)
{
assert(!empty());
Q = 1;
auto l = *lower_bound({0, 0, x});
Q = 0;
return l.k * x + l.m;
}
ll getid(ll x)
{
assert(!empty());
Q = 1;
auto l = *lower_bound({0, 0, x});
Q = 0;
return l.id;
}
};
ll n, k, dp[MAXS][MAXN], par[MAXS][MAXN], a[MAXN], part[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
part[i] = part[i - 1] + a[i];
for (int i = 1; i <= k; i++)
{
CHT cur;
cur.add(part[i], dp[1 - i % 2][i] - part[i] * part[i], i);
for (int j = i + 1; j <= n; j++)
{
dp[i % 2][j] = cur.query(part[j]);
par[i][j] = cur.getid(part[j]);
cur.add(part[j], dp[1 - i % 2][j] - part[j] * part[j], j);
}
}
cout << dp[k % 2][n] << "\n";
int t = k, last = n;
while(t)
{
cout << par[t][last] << " ";
last = par[t][last];
t--;
}
}
