#include <bits/stdc++.h>
#define N 100005
#define K 202
#define inf 200000000000000000LL
#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];
void fastscan(int &number)
{
register int c;
number = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
}
void fast_ll(ll &number)
{
register int c;
number = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
}
inline void addline(vector< pair<pii, int> > &line, 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 && (line[line.size() - 2].f.s - l.f.s) * (line[line.size() - 2].f.f - line[line.size() - 1].f.f) <=
(line[line.size() - 1].f.s - line[line.size() - 2].f.s) * (l.f.f - line[line.size() - 2].f.f)) line.pop_back();
line.push_back(l);
}
inline pair<ll, int> query(vector< pair<pii, int> > &line, int x)
{
int p = line.size();
if(r >= p) r = p - 1;
while(r < p - 1 && line[r].f.f*x + line[r].f.s > line[r + 1].f.f*x + line[r + 1].f.s)r++;
return pii(line[r].f.f*x + line[r].f.s, line[r].s);
}
int32_t main()
{
//ios::sync_with_stdio(false); cin.tie(0);
fastscan(n), fastscan(k);
for(int i = 1; i <= n; i++) fast_ll(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;
int A = 1, B = 0;
for(int q = 1; q <= k ; q++)
{
vector< pair<pii, int> > line;
for(int i = n - 1; i >= 1; i--)
{
addline(line, make_pair(pii( -sum[i], -(sum[i]*sum[n] - sum[i]*sum[i] + dp[i + 1][ B ] )), i));
pair<ll, int> best = query(line, sum[i - 1]);
dp[i][A] = -best.f - sum[i - 1]*sum[n];
prox[i][q] = best.s;
}
swap(A, B);
}
printf("%lld\n", dp[1][k%2]);
int ini = 1, q = k;
while(true)
{
if(!prox[ini][q]) break;
qtd ++;
block[prox[ini][q]] = 1;
printf("%d ", prox[ini][q]);
ini = prox[ini][q] + 1;
q --;
}
int extra = k - qtd;
for(int i = 1, cnt = 0; i <= n && cnt < extra; i++)
{
if(!block[i]) printf("%d ", i), cnt ++;
}
cout<<"\n";
}
