#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 5, maxk = 205;
ll dp[2][maxn], pf[maxn];
int split[maxk][maxn];
int n, k;
inline ll sum(const int& l, const int& r)
{
return pf[r + 1] - pf[l];
}
void rek(int i, int l1, int l2, int r1, int r2)
// chceme zistit odpovede pre dp[i][l1] az dp[i][l2] ak optimalne splity musia lezat v intervale [r1, r2]
{
if (l1 > l2) return;
int mid = (l1 + l2) >> 1;
int best = -1, id = -1;
for (int j = max(r1, mid); j <= r2; j++)
{
ll val = sum(mid, j) * sum(j + 1, n - 1) + dp[(i & 1) ^ 1][j + 1];
if (val > best)
{
id = j;
best = val;
}
}
dp[i&1][mid] = best;
split[i][mid] = id;
rek(i, l1, mid - 1, r1, id);
rek(i, mid + 1, l2, id, r2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 0, a; i < n; i++)
{
cin >> a;
pf[i + 1] = pf[i] + a;
}
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < n; j++)
{
dp[i & 1][j] = 0;
}
rek(i, 0, n - 2, 0, n - 2);
}
cout << dp[k&1][0] << "\n";
for (int i = k, j = 0; i > 0; i--)
{
j = split[i][j]+1;
cout << j << " ";
}
cout << "\n";
return 0;
}
