/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <cassert>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n,k,st;
LL a[100005],pr[100005],dp[10004][202];
int nxt[10004][202];
LL sum(int l, int r)
{
return pr[r] - pr[l - 1];
}
void dfs(int l,int k)
{
if (k == 0)
dp[l][k] = 0;
if (dp[l][k] != -1)
return;
for (int i = l; i < n && n-i+1>=k; i++)
{
dfs(i+1,k-1);
LL d = sum(l, i)*sum(i + 1, n) + dp[i+1][k-1];
if (d > dp[l][k])
{
dp[l][k] = d;
nxt[l][k] = i;
}
}
}
void print(int l,int k)
{
if (k <= 0)
return;
int p = nxt[l][k];
cout << p << " ";
k--;
print(p+1,k);
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pr[i] = pr[i - 1] + a[i];
}
for (int i = 1; i <= n; i++)
for (int p = 1; p <= k; p++)
dp[i][p] = -1;
dfs(1,k);
cout << dp[1][k] << endl;
print(1,k);
cout << endl;
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
