#include <bits/stdc++.h>
typedef long long ll;
const ll N = 1e5 + 1, K = 201;
const ll inf = 1e15;
ll dp[K][N];
ll a[N], psum[N];
ll sum(ll a, ll b) {
if (a > b) {
return 0;
}
ll ans = psum[b];
if (a - 1 >= 0) {
ans -= psum[a - 1];
}
return ans;
}
struct Line {
int m;
ll b;
ll eval(ll x) {
return m * x + b;
}
};
class CHT {
private:
bool parallel(const Line &a, const Line &b) {
return a.m == b.m;
}
long double x_intersection(const Line &a, const Line &b) {
return (a.b - b.b) / ((long double) (b.m - a.m));
}
public:
std::deque<Line> dq;
void insert(Line l) {
if (dq.size() >= 1 && parallel(l, dq.back()) && l.b <= dq.back().b) {
return;
}
while (dq.size() >= 2) {
if (parallel(l, dq.back())) {
if (l.b > dq.front().b) {
dq.pop_front();
continue;
} else {
return;
}
}
if (x_intersection(l, dq.back()) <= x_intersection(dq.back(), dq[dq.size() - 2])) {
dq.pop_back();
} else {
break;
}
}
if (dq.size() == 1 && parallel(l, dq.back()) && l.b > dq.back().b) {
dq.pop_back();
}
dq.push_back(l);
}
ll query(ll x) {
while (dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x)) {
dq.pop_front();
}
return dq[0].eval(x);
}
};
int main() {
ll n, k;
std::cin >> n >> k;
for (ll i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::partial_sum(a, a + n, psum);
if (n == 2) {
std::cout << a[0] * a[1] << "\n1\n";
return 0;
}
for (ll i = 0; i <= k; ++ i) {
CHT hull;
for (ll j = n - 1; j >= 0; -- j) {
if (j == n - 1) {
dp[i][j] = -inf * (i != 0);
continue;
}
if (i == 0) {
dp[i][j] = 0;
continue;
}
int m = sum(j + 1, n - 1);
ll b = dp[i - 1][j + 1] + sum(0, j) * sum(j + 1, n - 1);
hull.insert({m, b});
ll ans = hull.query(-sum(0, j - 1));
dp[i][j] = std::max(0LL, ans);
}
}
std::cout << dp[k][0] << "\n";
ll i = 0;
ll ops = k;
for (ll c = i; c < n - 1 && ops > 0; c++) {
if (dp[ops][i] == sum(i, c) * sum(c + 1, n - 1) + dp[ops - 1][c + 1]) {
std::cout << c + 1 << " ";
ops--;
i = c + 1;
}
}
}
