#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000'10;
vector<int> dp[2];
ll pref[N];
ll arr[N];
int pre[N][201];
ld slope(ll a, ll b) {
return (ld)(dp[0][a] - dp[0][b])/(-pref[b]+pref[a]);
}
ll val(ll idx, ll x) {
return (-pref[idx]*x) + dp[0][idx];
}
int main () {
ll n, k;
cin >> n >> k;
for(int i = 0;i<n;i++)
cin >> arr[i];
pref[0] = arr[0];
for(int i = 0;i<2;i++)dp[i].resize(n+1);
for(int i = 1;i<n;i++)pref[i] = pref[i-1]+arr[i];
for(int i = 0;i<=n;i++)pre[i][0] = -1;
for(int j = 1;j<=k;j++) {
deque<ll> dq;
for(int i = 0;i<n;i++) {
ll cur = i, x = pref[n-1]-pref[i], ans = 0;
while(dq.size() >= 2 && val(dq.back(), x) <=
val(dq[dq.size()-2], x))dq.pop_back();
if(dq.size()){
ans = val(dq.back(), x) + pref[i]*(pref[n-1]-pref[i]);
pre[i][j] = dq.back();
}
else {
ans = pref[i]*(pref[n-1]-pref[i]);
pre[i][j] = -1;
}
dp[1][i] = ans;
while(dq.size() >= 2 && slope(cur, dq[0])
>= slope(dq[0], dq[1]))dq.pop_front();
dq.push_front(cur);
}
dp[0].swap(dp[1]);
}
ll mx = -1, idx = -1;
for(int i = 0;i<n;i++) {
if(dp[0][i] >= mx) {
mx = dp[0][i];
idx = i;
}
}
cout << mx << "\n";
while(idx!=-1 and k > 0) {
cout << idx+1 << " ";
idx = pre[idx][k];
k--;
}
cout << "\n";
}
