#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e5+10, maxk = 210;
int a[maxn], suf[maxn];
int itv(int l, int r) { return suf[l] - suf[r+1]; }
long long dp[maxn][maxk];
int opt[maxn][maxk];
void solve(int l, int r, int l2, int r2, int k) {
if(l > r) return;
int m = (l+r) >> 1;
pair<long long, int> ans;
for(int i = min(m-1, r2); i >= l2; i--)
ans = max(ans, {dp[i][k-1] + 1ll * suf[m+1] * itv(i+1, m), i});
opt[m][k] = ans.second;
dp[m][k] = ans.first;
solve(l, m-1, l2, ans.second, k);
solve(m+1, r, ans.second, r2, k);
}
int main() {
int n, k; scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", a+i);
for(int i = n; i >= 1; i--)
suf[i] = suf[i+1] + a[i];
for(int i = 1; i <= k; i++)
solve(1, n-1, 0, n-1, i);
pair<long long, int> best;
vector<int> ans;
for(int i = 1; i <= n; i++)
best = max(best, {dp[i][k], i});
int i = best.second;
while(i)
ans.push_back(i), i = opt[i][k], --k;
printf("%lld\n", best.first);
reverse(ans.begin(), ans.end());
for(int x : ans)
printf("%d ", x);
puts("");
}
