#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll INF = 1e18;
int a[N]; ll f[N];
pair<ll, int> dp[205][N];
#define fi first
#define se second
int n, m;
void task1() {
for (int k = 2; k <= m; ++k) {
for (int i = 1; i <= n; ++i) {
dp[k][i].fi = -INF;
for (int j = i - 1; ~j; --j) {
ll sum = dp[k - 1][j].fi + f[j] * (f[i] - f[j]);
dp[k][i] = max(dp[k][i], make_pair(sum, j));
}
}
}
cout << dp[m][n].fi << '\n';
vector<int> path;
for (int j = m, i = dp[m][n].se; i; j--, i = dp[j][i].se) {
path.emplace_back(i);
}
reverse(path.begin(), path.end());
for (int i : path) cout << i << ' ';
}
struct Line {
ll a, b;
int i;
Line() = default;
Line(ll a, ll b, int i): a(a), b(b), i(i) {}
ll get(int x) {
return a * x + b;
}
} dq[N];
int front, back;
using ld = long double;
int better(const Line& a, const Line& b, const Line& c) {
// (a1-a2) * x = b2-b1
// x = (b2 - b1) / (a1 - a2)
return (ld)(a.b - b.b) / (a.a - b.a) >= (ld)(a.b - c.b) / (a.a - c.a);
}
void insert(ll a, ll b, int i) {
Line l(a, b, i);
while (back > front && better(l, dq[back], dq[back - 1])) {
back--;
}
dq[++back] = l;
}
pair<ll, int> get(int x) {
while (front < back && dq[front].get(x) <= dq[front + 1].get(x)) {
front++;
}
return make_pair(dq[front].get(x), dq[front].i);
}
int main() {
cin.tie(0)->sync_with_stdio(0); cout.tie(0);
cin >> n >> m; m++;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
f[i] = f[i - 1] + a[i];
}
// if (n <= 1000) {
// task1();
// return 0;
// }
for (int k = 2; k <= m; ++k) {
front = 0, back = -1;
for (int i = 1; i <= n; ++i) {
insert(f[i - 1], dp[k - 1][i - 1].fi - f[i - 1] * f[i - 1], i - 1);
// sum = f[j] * f[i] + dp[k - 1][j].fi - f[j] * f[j];
dp[k][i] = get(f[i]);
}
}
cout << dp[m][n].fi << '\n';
int i = m, j = n;
while (i > 1) {
cout << dp[i][j].se << ' ';
j = dp[i][j].se; i--;
}
return 0;
}
