#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
int A[100005];
ll B[100005];
ll sum(int a, int b)
{
return B[b] - B[a-1];
}
ll dp[2][100005];
int opt[205][100005];
void solve(int k, int L, int R, int i, int j)
{
if(L> R) return;
int M = (L+R)/2;
ll best = -1e9;
int add = 0;
//printf("dp[%d][%d]:\n", k, M);
for(int p = max(i, 2); p<= min(j, M); p++)
{
ll here = dp[1-k%2][p-1] + sum(1, p-1)*sum(p, M);
//printf("p = %d %lld %lld = %lld\n", p, dp[k-1][p-1], sum(1, p-1)*sum(p, M), here);
if(here> best)
{
best = here;
add = p;
}
}
dp[k%2][M] = best;
opt[k][M] = add;
//printf("dp[%d][%d] = %lld\n", k, M, best);
solve(k, L, M-1, i, add);
solve(k, M+1, R, add, j);
}
int main()
{
//freopen("50", "r", stdin);
//freopen("50.out", "w", stdout);
int n, k; scanf("%d %d", &n, &k);
k++;
for(int i = 1; i<= n; i++)
{
scanf("%d", A+i);
B[i] = B[i-1] + A[i];
}
for(int i = 1; i<= n; i++) dp[1][i] = 0;
for(int i = 2; i<= k; i++) solve(i, 1, n, 1, n);
printf("%lld\n", dp[k%2][n]);
vector<int> cut;
int remk = k, remn = n;
while(remk>0 && remn>= 0)
{
if(opt[remk][remn]) cut.pb(opt[remk][remn]-1);
else break;
remn = opt[remk][remn]-1;
remk--;
}
reverse(cut.begin(), cut.end());
for(auto x : cut) printf("%d ", x);
return 0;
}
