#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, K = 205;
int n, k, lvl, w, P[K][N];
ll A[N], dp[2][N];
inline ll Get(int l, int r)
{
return ((A[r] - A[l]) * (A[r] - A[l]));
}
void Solve(int l, int r, int le, int ri)
{
if (r < l)
return ;
int md = (l + r) >> 1, opt = -1;
ll Mn = 2e18;
for (int i = le; i <= min(ri, md); i++)
if (Mn >= Get(i - 1, md) + dp[!w][i - 1])
Mn = Get(i - 1, md) + dp[!w][i - 1], opt = i;
dp[w][md] = Mn;
P[lvl][md] = opt - 1;
Solve(l, md - 1, le, opt);
Solve(md + 1, r, opt, ri);
}
int main()
{
ll sum = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld", &A[i]), A[i] += A[i - 1];
memset(dp, 63, sizeof(dp)); dp[0][0] = 0;
for (lvl = 1; lvl <= k + 1; lvl ++)
w = lvl & 1, Solve(1, n, 1, n), dp[0][0] = 2e18;
printf("%lld\n", (A[n] * A[n] - dp[w][n]) >> 1);
vector < int > vec;
for (int i = k + 1, nw = P[i][n]; i > 1; i--, nw = P[i][nw])
vec.push_back(nw);
reverse(vec.begin(), vec.end());
for (int i : vec) printf("%d ", i);
return 0;
}
