#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], e;
ll dp[N][3], sum[N];
ll A[N], B[N], ID[N];
inline void fastscan(int &number)
{
register int c;
number = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
}
inline 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(pair<pii, int> l)
{
if(e && A[e - 1] == l.f.f)
{
if(B[e - 1] < l.f.s) return;
if(B[e - 1] == l.f.s && ID[e - 1] < l.s) return;
A[e - 1] = l.f.f, B[e - 1] = l.f.s, ID[e - 1] = l.s;
return;
}
while(e >= 2 && (B[e - 2] - l.f.s) * (A[e - 1] - A[e - 1]) <=
(B[e - 1] - B[e - 2]) * (l.f.f - A[e - 1])) e--;
e++;
A[e - 1] = l.f.f, B[e - 1] = l.f.s, ID[e - 1] = l.s;
}
inline pair<ll, int> query( int x)
{
if(r >= e) r = e - 1;
while(r < e - 1 && A[r]*x + B[r] > A[r + 1]*x + B[r + 1])r++;
return pii(A[r]*x + B[r], ID[r]);
}
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++)
{
e = 0;
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][ B ] )), i));
pair<ll, int> best = query(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";
}
