#include <bits/stdc++.h>
#define N 100005
#define K 202
#define inf 2000000000000000
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
int n, k, r, block[N], qtd, prox[N][K];
ll dp[N][3], sum[N];
vector< pair<pii, int> > line;
ll F(ll x, int id)
{
return line[id].f.f*x + line[id].f.s;
}
double intersect(pii r, pii s)
{
return ((double)(r.s - s.s))/((double)(s.f - r.f));
}
bool bad(pii A, pii B, pii C)
{
return intersect(A, C) > intersect(B, A);
}
void addline(pair<pii, int> l)
{
if(line.size() && line.back().f.f == l.f.f)
{
if(line.back().f.s < l.f.s) return;
if(line.back().f.s == l.f.s && line.back().s < l.s) return;
line.pop_back();
line.push_back(l);
return;
}
while(line.size() >= 2 && bad( line[line.size() - 2].f, line.back().f, l.f )) line.pop_back();
line.push_back(l);
}
pii query(int x)
{
pii best = pii(inf, -1);
int p = line.size();
if(r >= p) r = p - 1;
while(r < p - 1 && F(x, r) > F(x, r + 1))r++;
return pii(F(x, r), line[r].s);
}
void print(int ini, int k)
{
if(!prox[ini][k]) return;
qtd ++;
block[prox[ini][k]] = 1;
cout<<prox[ini][k]<<" ";
print(prox[ini][k] + 1, k - 1);
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k;
for(int i = 1; i <= n; i++) cin>>sum[i], sum[i] += sum[i - 1];
for(int i = 0; i <= n; i++) dp[i][0] = 0;
for(int i = 0; i <= k; i++) dp[n][i] = 0;
for(int q = 1; q <= k ; q++)
{
for(int i = n - 1; i >= 1; i--)
{
addline(make_pair(pii( -sum[i], -(sum[i]*sum[n] - sum[i]*sum[i] + dp[i + 1][ (q + 1)%2 ] )), i));
pii best = query(sum[i - 1]);
dp[i][q%2] = -best.f - sum[i - 1]*sum[n];
prox[i][q] = best.s;
}
line.clear();
r = 0;
}
cout<<dp[1][k%2]<<"\n";
print(1, k);
int extra = k - qtd;
for(int i = 1, cnt = 0; i <= n && cnt < extra; i++)
{
if(!block[i]) cout<<i<<" ", cnt ++;
}
cout<<"\n";
}
