#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int mx = 100005;
struct CHT{
ll A[mx], B[mx];
int I[mx];
int p, sz;
pli query(ll x){
while(p + 1 < sz && (A[p+1] - A[p]) * x <= B[p] - B[p+1]) ++p;
return {A[p] * x + B[p], I[p]};
}
void insert(ll a, ll b, int i){
//printf("----inserting y = %lld x + %lld, idx = %d----\n",a,b,i);
A[sz] = a;
B[sz] = b;
I[sz] = i;
while(p + 1 < sz && (B[sz-2] - B[sz]) * (A[sz] - A[sz-1]) <= (A[sz] - A[sz-2]) * (B[sz-1] - B[sz])){
//printf("removing y = %lld x + %lld\n",A[sz-1],B[sz-1]);
A[sz-1] = A[sz];
B[sz-1] = B[sz];
I[sz-1] = I[sz];
--sz;
}
++sz;
}
void clear(){
sz = p = 0;
}
} C;
int a[mx], S[mx];
int n, k;
ll D[mx][2];
int bck[mx][205];
void input(){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> S[i];
S[i] += S[i-1];
}
}
void fucking_cht(){
for(int i = 1; i <= n; i++) D[i][0] = 2e18;
for(int l = 1, w = 1; l <= k + 1; l++, w ^= 1){
//printf("lev = %d\n",l);
C.clear();
C.insert(0,0,0);
for(int i = l-1; i <= n; i++){
if(i >= l){
tie(D[i][w],bck[i][l]) = C.query(S[i]);
D[i][w] += (ll)S[i] * S[i];
//printf("D[%d][%d] = %lld\n",i,l,D[i][w]);
}
C.insert(-2LL * S[i], D[i][!w] + (ll)S[i] * S[i], i);
}
}
cout << ((ll)S[n] * S[n] - D[n][(k+1)&1])/2 << '\n';
stack<int> trace;
for(int i = k+1, now = n; i >= 1; i--){
trace.push(bck[now][i]);
now = bck[now][i];
}
trace.pop();
for(int i=0;i<k;i++){
cout << trace.top() << ' ';
trace.pop();
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
input();
fucking_cht();
}
