#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int N=1e5+5;
int n, k, a[N], b[205][N], pd[N];
ll dp[N], dd[N];
void sol(int i, int l, int r, int lx, int rx){
int m=(l+r)/2;
pli x={dp[lx]+1LL*pd[lx]*(pd[m]-pd[lx]), lx};
for(int j=lx+1;j<min(m, rx+1);++j)
x=max(x, {dp[j]+1LL*pd[j]*(pd[m]-pd[j]), j});
dd[m]=x.F;
b[i][m]=x.S;
if(l<m)
sol(i, l, m, lx, x.S);
if(m+1<r)
sol(i, m+1, r, x.S, rx);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
pd[i]=a[i]+pd[i-1];
}
for(int i=1;i<=k;++i){
sol(i, 1, n+1, 0, n-1);
for(int j=1;j<=n;++j)
dp[j]=dd[j];
}
cout<<dp[n]<<'\n';
vector<int>v;
int h=n;
for(int i=k;i>0;--i){
h=b[i][h];
v.push_back(h);
}
for(int i=k-1;i>=0;--i)
cout<<v[i]<<' ';
cout<<'\n';
}
