#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
typedef long long ll;
const ll maxn = 1e5 + 16 , inf = 2e18;
ll a[maxn] , ps[maxn] , dp[maxn] , pd[maxn];
int opt[216][maxn];
ll cost(ll l , ll r){
ll res = ps[r] - (l ? ps[l - 1] : 0);
res *= res;
return res;
}
void dv(ll l , ll r , ll opl , ll opr , ll j){
if(l >= r) return;
ll m = (r + l) >> 1 , lm = min(m - 1 , opr);
dp[m] = inf;
ll ind = -1;
for(ll i = opl ; i <= lm ; i++){
ll h = pd[i] + cost(i + 1 , m);
if(h < dp[m]){
dp[m] = h;
ind = i;
}
}
opt[j][m] = ind;
dv(l , m , opl , ind , j); dv(m + 1 , r , ind , opr , j);
return;
}
vector<ll> v;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n , k;
cin>>n>>k;
for(ll i = 0 ; i < n ; i++){
cin>>a[i];
}
ps[0] = a[0];
for(ll i = 1 ; i < n ; i++){
ps[i] = ps[i - 1] + a[i];
}
for(ll i = 0 ; i < n ; i++){
pd[i] = ps[i] * ps[i];
}
for(ll j = 1 ; j <= k ; j++){
dv(j , n , j - 1 , n - 1 , j);
memcpy(pd , dp , sizeof(dp));
}
// for(ll i = 0 ; i < n ; i++){
// cout<<pd[i]<<' ';
// }
// cout<<'\n';
ll h = ps[n - 1] * ps[n - 1] - dp[n - 1]; h >>= 1ll;
cout<<h<<'\n';
ll p = n - 1 , j = k;
while(~j){
v.push_back(p);
p = opt[j--][p];
}
reverse(all(v));
for(ll i = 0 ; i < k ; i++){
cout<<v[i] + 1<<' ';
}
cout<<'\n';
return 0;
}
