#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <cassert>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <unordered_map>
#include <chrono>
#define int long long
#define ii pair<int, int>
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
using namespace std;
int n, k, a[10005], pref[10005], l = 1, r, cur, now;
ii f[100005][205];
vector <int> part;
void dp(int u, int v, int x, int y) {
if (u > v) return;
int mid = (u + v) >> 1;
for (int i = x; i <= min(y, mid - 1); i++)
{
cur = (pref[i] - pref[mid]) * (pref[i] - pref[mid]);
//cout << i << ' ' << cur << endl;
if(f[i][now - 1].fi + cur <= f[mid][now].fi)
f[mid][now] = mp(f[i][now - 1].fi + cur, i);
}
dp(u, mid - 1, x, f[mid][now].se), dp(mid + 1, v, f[mid][now].se, y);
}
signed main() {
cin >> n >> k;
k++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
f[i][j] = {1e9, -1};
for(int i = 1; i <= n; i++)
{
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) f[i][1] = mp(pref[i] * pref[i], -1);
for (int i = 2; i <= k; i++) now = i, dp(1, n, 0, n - 1);
cur = f[n][k].se;
for (int i = k - 1; i > 0; i--)
{
part.pb(cur);
cur = f[cur][i].se;
}
cout << (pref[n] * pref[n] - f[n][k].fi) / 2 << endl;
reverse(part.begin(), part.end());
for (int i = 0; i < part.size(); i++)
cout << part[i] << ' ';
}
