#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'
struct line
{
ll m, b, ind;
pll calc(int x)
{
return {m*x+b, ind};
}
};
struct node
{
node *l=nullptr, *r=nullptr;
line *ln=nullptr;
};
void update(node* cur, line* lin, int l, int r)
{
int m=(l+r)/2;
if(cur->ln==nullptr) {cur->ln=lin;return;}
if(lin->calc(m)>cur->ln->calc(m)) swap(lin, cur->ln);
if(l==r) {delete lin;return;}
if(cur->ln->calc(l)<lin->calc(l))
{
if(cur->l==nullptr) cur->l = new node();
update(cur->l, lin, l, m);
}
if(cur->ln->calc(r)<lin->calc(r))
{
if(cur->r==nullptr) cur->r = new node();
update(cur->r, lin, m+1, r);
}
}
pll query(int x, node* cur, int l, int r)
{
if(!cur) return {-LLONG_MAX, 0};
pll res = (cur->ln ? cur->ln->calc(x) : make_pair(-LLONG_MAX, 0ll));
if(l==r) return res;
int m=(l+r)/2;
if(x<=m&&cur->l) return max(res, query(x, cur->l, l, m));
if(x>m&&cur->r) return max(res, query(x, cur->r, m+1, r));
return res;
}
node* root=new node();
node* newroot=new node();
main()
{
cin.tie(0) -> sync_with_stdio(0);
// for(int i = 0;i < 200;i++) root[i]=new node();
int n, k;
cin >> n >> k;
int a[n+1];
ll pref[n+1]={}, sum=0;
int last[n+1][k+1]={};
a[0]=0;
for(int i = 1;i <= n;i++) {cin >> a[i];pref[i]=pref[i-1]+a[i];sum+=a[i];}
ll mx=-3;
int asd=0;
for(int i = 0;i <= n;i++) last[i][0]=0;
update(root, new line{0, 0, 0}, 0, 1e9);
for(int x=1;x<=k;x++)
{
for(int i = 1;i <= n;i++)
{
if(x>i) continue;
auto[val, ind]=query((pref[n]-pref[i]), root, 0, 1e9);
ll asdsa=val+((pref[n]-pref[i])*pref[i]);
if(asdsa>mx)
{
mx=asdsa;
asd=i;
}
if(x!=k) update(newroot, new line{-pref[i], asdsa, i}, 0, 1e9);
last[i][x]=ind;
}
root=newroot;
newroot= new node();
}
cout << mx << endl;
int cur=k, j=asd;
cout << j << " ";
while(cur!=1)
{
cout << last[j][cur] << " ";
j=last[j][cur];
cur--;
}
return 0;
}
