/**
* Prof.Nicola
**/
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
struct line
{
long long slope,constant,idx;
void def(long long x,long long z,long i)
{
slope=x;
constant=z;
idx=i;
}
long long sub(long long x)
{
return (x*slope)+constant;
}
bool operator==(const line&x)const
{
if(slope==x.slope&&constant==x.constant){
return true;
}
return false;
}
bool operator<(const line&x)const
{
if(slope<x.slope){
return true;
}
if(slope==x.slope){
return (constant<x.constant);
}
return false;
}
bool operator<=(const line&x)const
{
if(slope==x.slope&&constant==x.constant){
return true;
}
if(slope<x.slope){
return true;
}
if(slope==x.slope){
return (constant<x.constant);
}
return false;
}
bool operator>(const line&x)const
{
if(slope>x.slope){
return true;
}
if(slope==x.slope){
return (constant>x.constant);
}
return false;
}
bool operator>=(const line&x)const
{
if(slope==x.slope&&constant==x.constant){
return true;
}
if(slope>x.slope){
return true;
}
if(slope==x.slope){
return (constant>x.constant);
}
return false;
}
};
long long intersection(line x,line z)
{
return ((x.constant-z.constant)/(z.slope-x.slope));
}
bool parallel(line x,line z)
{
if(x.slope==z.slope){
return true;
}
return false;
}
struct set_of_lines
{
set<line>s;
set<line>::iterator t;
long long intersect;
map<line,pair<long long,long long> >range;
map<long long,line>line_;
set<long long>intervals;
pair<long long,long long>p;
void add(line x)
{
if(s.count(x)){
return;
}
range[x]=mp(-1e18,1e18);
s.insert(x);
t=s.find(x);
t--;
while(!(t==s.end())&&!(x==*t)){
if(parallel(x,*t)){
s.erase(x);
return;
}
intersect=intersection(x,*t);
p=range[*t];
if(intersect>=p.second){
intervals.erase(range[*t].first);
s.erase(*t);
}
else if(p.first<=intersect&&intersect<p.second){
intervals.erase(range[*t].first);
range[x].second=intersect;
range[*t].first=intersect+1;
intervals.insert(range[*t].first);
line_[range[*t].first]=*t;
break;
}
else{
range[x].second=p.first-1;
break;
}
t=s.find(x);
t--;
}
t=s.find(x);
t++;
while(!(t==s.end())){
if(parallel(x,*t)){
intervals.erase(range[*t].first);
s.erase(*t);
t=s.find(x);
t++;
continue;
}
intersect=intersection(x,*t)+1;
p=range[*t];
if(intersect<=p.first){
intervals.erase(range[*t].first);
s.erase(*t);
}
else if(p.first<intersect&&intersect<=p.second){
intervals.erase(range[*t].first);
range[x].first=intersect;
range[*t].second=intersect-1;
intervals.insert(range[*t].first);
line_[range[*t].first]=*t;
break;
}
else{
range[x].first=p.second+1;
break;
}
t=s.find(x);
t++;
}
if(range[x].first>range[x].second){
s.erase(x);
}
else{
intervals.insert(range[x].first);
line_[range[x].first]=x;
}
}
pair<long long,long> get(long long x)
{
long long z=sLE(x,intervals);
return mp(line_[z].sub(x),line_[z].idx);
}
};
vector<long long>pre;
long long f(long l,long r)
{
if(l==0){
return pre[r];
}
return pre[r]-pre[l-1];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n,k;
cin>>n>>k;
vector<long long>v(n);
pre.resize(n);
re(v);
pre[0]=v[0];
REP(i,1,n){
pre[i]=pre[i-1]+v[i];
}
vector<set_of_lines>sol(k+1);
vector<vector<long long> >dp(n,vector<long long>(k+1));
vector<vector<long long> >from(n,vector<long long>(k+1));
REP(i,0,n){
dp[i][0]=0;
}
pair<long long,long>p;
line l;
l.def(0,0,0);
sol[0].add(l);
REP(i,1,n){
PER(j,1,k+1){
if(j>i){
continue;
}
p=sol[j-1].get(f(i,n-1));
from[i][j]=p.second;
dp[i][j]=-(p.first-(f(0,i-1)*f(i,n-1)));
l.def(f(0,i-1),-dp[i][j],i);
sol[j].add(l);
}
}
long long mx=0,x;
REP(i,k,n){
if(dp[i][k]>mx){
mx=dp[i][k];
x=i+1;
}
}
cout<<mx<<endl;
REP(i,0,k){
cout<<x<<" ";
x=from[x][k-i];
}
return 0;
}
