#include <bits/stdc++.h>
#define int long long
using namespace std;
const int oo = INT_MAX;
int n,k;
int v[100005];
int sp[100005];
int dp[100005][2];
signed l[100005][205];
int d[100005];
int sum(int st, int dr)
{
if(st > dr)
{
return 0;
}
return sp[dr] - sp[st - 1];
}
long double time_bigger(int a, int b, int j)
{
pair<int,int> line_a = {sp[a],dp[a][j % 2]};
pair<int,int> line_b = {sp[b],dp[b][j % 2]};
return 1.0 * (line_b.second - line_a.second) / (line_a.first - line_b.first);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
++k;
for(int i=1; i<=n; i++)
{
cin>>v[i];
sp[i] = sp[i-1] + v[i];
}
for(int i=1; i<=n; i++)
{
dp[i][1] = sum(1,i) * sum(i + 1, n);
}
for(int j=2; j<=k; j++)
{
int p = 1, u = 0;
for(int i=1; i<=n; i++)
{
while(p<u && time_bigger(d[p+1],d[p],j-1) <= -1.0 * (sp[n] - sp[i]))
{
++p;
}
int poz = d[p];
if(p<=u)
{
dp[i][j % 2] = dp[poz][(j-1) % 2] + sum(poz + 1,i) * sum(i + 1, n);
l[i][j] = poz;
}
else
{
dp[i][j % 2] = -oo;
}
while(p<u && time_bigger(i,d[u],j-1) < time_bigger(d[u],d[u-1],j-1))
{
--u;
}
d[++u] = i;
}
}
cout<<dp[n][k % 2]<<'\n';
int poz = n;
vector<int> rez;
while(poz)
{
poz = l[poz][k--];
if(poz)
{
rez.push_back(poz);
}
}
reverse(rez.begin(),rez.end());
for(auto it : rez)
{
cout<<it<<' ';
}
cout<<'\n';
return 0;
}
