#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)
int main() {
ll N,K;
cin >> N >> K;
vector<ll> A(N);
rep(i,N) cin >> A[i];
vector<ll> sum(N+1);
sum[0]=0;
rep(i,N) sum[i+1]=sum[i]+A[i];
ll ans=0;
set<ll> s;
s.insert(0);
s.insert(N);
rep(i,K){
ll cnt1=0,cnt2=-1;
auto itl=s.begin();
auto itr=s.begin();
itr++;
while(itr!=s.end()){
for(ll j=*itl+1;j<*itr;j++){
if(cnt1<(sum[j]-sum[*itl])*(sum[*itr]-sum[j])){
cnt1=(sum[j]-sum[*itl])*(sum[*itr]-sum[j]);
cnt2=j;
}
}
itl++;
itr++;
}
ans+=cnt1;
s.insert(cnt2);
}
cout << ans << endl;
s.erase(0);
s.erase(N);
auto it=s.begin();
while(it!=s.end()){
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
