#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const ll INF = (ll)1.1e18;
ll slow(int n, int k, vector<ll> a, vector<int> &c) {
vector<ll> pref(n + 1, 0);
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
auto cost = [&](int l, int r)->ll {
return (pref[r] - pref[l]) * (pref[r] - pref[l]);
};
vector<vector<int>> opt(k + 1, vector<int>(n, -1));
vector<ll> dp(n + 1, INF);
for (int i = 1; i <= n; i++) dp[i] = cost(0, i);
for (int t = 1; t <= k; t++) {
vector<ll> ndp(n + 1, INF);
for (int i = 0; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] + cost(j, i) < ndp[i]) ndp[i] = dp[j] + cost(j, i), opt[t][i] = j;
}
}
dp.swap(ndp);
}
ll res = (cost(0, n) - dp[n]) / 2;
int cur = n;
for (int i = k; i >= 0; i--) {
if (i != k) c.push_back(cur);
cur = opt[i][cur];
}
reverse(c.begin(), c.end());
return res;
}
ll fast(int n, int k, vector<ll> a, vector<int> &c) {
return 0;
}
void rofl() {
cout << "roflan pominki" << endl;
exit(0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<ll> a(n);
for (ll &x : a) cin >> x;
if (n <= 0 || k <= 0 || k >= n || *min_element(a.begin(), a.end()) < 0 || *max_element(a.begin(), a.end()) > (ll)1e4) rofl();
vector<int> c;
if (1) cout << slow(n, k, a, c); else cout << fast(n, k, a, c);
cout << endl;
for (int i : c) cout << i << " ";
cout << endl;
return 0;
}
