#include <bits/stdc++.h>
#define hash _hash_
#define y1 _y1_
#define dec _dec_
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll MOD = 1e9 + 7;
const ll oo = (ll)1e18;
/*------------- I alone decide my fate ! -------------*/
/* Chiec den ong sao, sao 5 canh tuoi mau... */
const int MAXN = 100009;
const int MAXK = 205;
int N, K, a[MAXN];
ll pre[MAXN];
// dp hai chiều bị xoá — thay bằng 1 chiều
int par[MAXN][MAXK]; // mở đủ lớn như bạn yêu cầu
// Convex Hull Trick - maximum (CHT - Convex Hull Trick)
struct Line {
ll m, b; // y = m*x + b
int idx; // lưu vị trí k
long double interX(const Line &other) const {
return (long double)(other.b - b) / (m - other.m);
}
};
struct CHT {
deque<Line> dq;
void add(ll m, ll b, int idx) {
Line l = {m,b,idx};
while(dq.size() >= 2) {
auto &l1 = dq[dq.size()-2], &l2 = dq.back();
// giữ nguyên so sánh như bản gốc (chú ý overflow có thể xảy ra trong một số test cực lớn)
if ((l2.b - l1.b) * (l1.m - l.m) >= (l.b - l1.b) * (l1.m - l2.m)) dq.pop_back();
else break;
}
dq.push_back(l);
}
pair<ll,int> query(ll x) {
while(dq.size() >= 2) {
auto &l1 = dq[0], &l2 = dq[1];
if (l2.m * x + l2.b >= l1.m * x + l1.b) dq.pop_front();
else break;
}
return {dq[0].m * x + dq[0].b, dq[0].idx};
}
};
void solve() {
cin >> N >> K;
for (int i = 1; i <= N; i ++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
// init par
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= K; ++j)
par[i][j] = -1;
// dp 1 chiều: dp_prev = dp[...][j-1], dp_cur = dp[...][j]
vector<ll> dp_prev(N+1, -oo), dp_cur(N+1, -oo);
dp_prev[0] = 0; // dp[0][0] = 0; dp[0][j>0] = -oo (sẽ tự nhiên)
for (int j = 1; j <= K; ++j) {
CHT cht;
// giữ hành vi như code gốc (thêm line (0,0,0) mỗi j)
cht.add(0, 0, 0); // tương đương k=0 theo code gốc
// reset dp_cur
fill(dp_cur.begin(), dp_cur.end(), -oo);
for (int i = 1; i <= N; ++i) {
auto [val, k] = cht.query(pre[i]);
dp_cur[i] = val; // giống bản gốc: dp[i][j] = value returned
par[i][j] = k;
// thêm dòng mới dùng giá trị dp_prev[i] (dp[i][j-1])
cht.add(pre[i], dp_prev[i] - pre[i]*pre[i], i);
}
// chuyển cột
dp_prev.swap(dp_cur);
}
cout << dp_prev[N] << "\n";
vector<int> cuts;
int ci = N, cj = K;
while (cj > 0) {
int t = par[ci][cj];
if (t == -1) break;
if (t > 0) cuts.push_back(t);
ci = t;
--cj;
}
reverse(cuts.begin(), cuts.end());
for (size_t i = 0; i < cuts.size(); ++i) {
if (i) cout << " ";
cout << cuts[i];
}
cout << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
solve();
return 0;
}
