#include <bits/stdc++.h>
using namespace std;
struct Line {
long long a, b;
int idx;
Line() {}
Line(long long _a, long long _b, int _idx) {
a = _a, b = _b, idx = _idx;
}
long long f(int x) {
return a * x + b;
}
~Line() {}
};
int sign(long long x) {
if (x > 0) { return 1; }
if (x < 0) { return -1; }
return 0;
}
long long intersect(const Line& A, const Line& B) {
// A.a * x + A.b = B.a * x + B.b
// x = (B.b - A.b) / (A.a - B.a)
long long numer = B.b - A.b, denom = A.a - B.a;
int sn = sign(numer), sd = sign(denom);
numer *= sn, denom *= sd;
if (sn * sd == -1) {
return numer / denom * (-1);
}
return (numer + denom - 1) / denom;
}
const int inf = 2e9;
struct CHT {
vector<long long> optX;
vector<Line> lines;
int ptr;
CHT() {
ptr = 0;
}
void clear() {
optX.clear();
lines.clear();
ptr = 0;
}
void insert(const Line& l) {
if (!lines.empty() && lines.back().a == l.a) {
if (l.b >= lines.back().b) {
return;
}
lines.pop_back();
optX.pop_back();
}
while (!lines.empty() && intersect(lines.back(), l) <= optX.back()) {
lines.pop_back();
optX.pop_back();
}
if (!lines.empty()) {
optX.emplace_back(intersect(lines.back(), l));
lines.emplace_back(l);
} else {
optX.emplace_back(-inf);
lines.emplace_back(l);
}
}
pair<long long, int> getVal(int x) {
ptr = min(ptr, (int)lines.size() - 1);
while (ptr + 1 < (int)lines.size() && optX[ptr + 1] <= x) {
++ptr;
}
assert(ptr < (int)lines.size());
return {lines[ptr].f(x), lines[ptr].idx};
}
~CHT() {}
};
const int maxn = 1e5, maxk = 201;
int par[maxn][maxk];
long long dp[maxn][2];
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n), pref(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
pref[i + 1] = pref[i] + a[i];
}
int layer = 0;
for (int i = 0; i < n; ++i) {
dp[i][0] = pref[i + 1] * 1ll * pref[i + 1];
par[i][0] = -1;
}
CHT cht;
for (int g = 1; g <= k; ++g) {
// cerr << "g: " << g << '\n';
layer ^= 1;
cht.clear();
pair<long long, int> res;
for (int i = g; i < n; ++i) {
// cerr << "i: " << i << '\n';
cht.insert(Line(-2 * pref[i], dp[i - 1][layer ^ 1] + pref[i] * 1ll * pref[i], i - 1));
// cerr << "inserted!\n";
res = cht.getVal(pref[i + 1]);
// cerr << "got!\n";
// cerr << "res: " << res.first + pref[i + 1] * 1ll * pref[i + 1] << '\n';
dp[i][layer] = res.first + pref[i + 1] * 1ll * pref[i + 1];
par[i][g] = res.second;
}
}
cout << (pref[n] * 1ll * pref[n] - dp[n - 1][layer]) / 2 << '\n';
vector<int> ans;
for (int i = n - 1, j = k; i >= 0 && j > 0; i = par[i][j], --j) {
// cerr << "i: " << i << '\n';
// cerr << "par: " << par[i][j] << '\n';
ans.emplace_back(par[i][j] + 1);
}
reverse(ans.begin(), ans.end());
for (const int& x : ans) {
cout << x << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
