#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
//#define int long long
#define inf 1000000000
#define pii pair<long long, long long>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
using namespace std;
int n, k;
int a[maxn];
long long pre[maxn];
long long sum(int l, int r)
{
return pre[r] - pre[l - 1];
}
struct CHT
{
vector<pair<int,pii>> line;
int pos = 0;
void clear()
{
line.clear();
pos = 0;
}
long long eval(pii a, int x)
{
return a.fi * x + a.se;
}
bool bad(pii a, pii b, pii c)
{
return (double)(b.se - a.se) / (a.fi - b.fi) <= (double)(c.se - a.se) / (a.fi - c.fi);
}
void add(pair<int,pii> newline)
{
line.pb(newline);
while (line.size() > 2 && bad(line[line.size() - 3].se, line[line.size() - 2].se, line.back().se))
line.erase(line.end() - 2);
}
pii get(long long x)
{
if (pos >= line.size())
pos = line.size() - 1;
while (pos < line.size() - 1 && eval(line[pos].se, x) <= eval(line[pos + 1].se, x))
pos++;
return make_pair(eval(line[pos].se, x),line[pos].fi);
}
};
namespace full
{
CHT cht;
long long dp[100010][2];
int trace[100010][200];
void solve()
{
fo(j, 1, k)
{
cht.clear();
cht.add({0,{0, 0}});
fo(i, 1, n)
{
pii now = cht.get(pre[n] - pre[i]);
dp[i][j % 2] = now.fi + pre[i] * (pre[n] - pre[i]);
if(j - 1 > 0)
trace[i][j] = now.se;
cht.add({i,{-pre[i], dp[i][1 - j % 2]}});
}
}
int pos = 0;
long long res = 0;
fo(i,k,n) if(res < dp[i][k % 2])
{
pos = i;
res = dp[i][k % 2];
}
if(res == 0)
{
cout << res << "\n";
fo(i,1,k) cout << i << ' ' ;
return ;
}
cout << res;en;
vi ans;
int j = k,id;
ans.pb(pos);
fo(i,1,k - 1)
{
pos = trace[pos][j--];
ans.pb(pos);
}
reverse(ans.begin(),ans.end());
for(int it : ans) cout << it << ' ';
}
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
fo(i, 1, n)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
full::solve();
}
