#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define pb push_back
#define int long long
typedef long double lld;
#define double lld
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 2e5;
vector<int>primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
void judge(){
srand(time(NULL));
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
freopen("Error.txt", "w", stderr);
#define debug(x...) cerr << #x <<" = "; _print(x); cerr << endl;
#else
#define debug(x...)
#endif
}
void usaco(string s) {
freopen((s + ".in").c_str(),"r",stdin);
freopen((s + ".out").c_str(),"w",stdout);
}
struct line {
mutable int m, c, p;
int pos;
bool operator<(const line& l) const { return m < l.m; }
bool operator<(int x) const { return p < x; }
};
// Returns max for a convex hull
struct LineContainer : multiset<line, less<>> {
// (for doubles, use inf = 1/.0, ceil(a,b) = a/b)
int div(int a, int b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(iterator x, iterator y) {
if (y == end()){
x -> p = inf;
return false;
}
if (x->m==y->m){
x->p = -1*inf;
if (x->c > y->c) {
x->p = inf;
}
}
else{
x->p = div(y->c - x->c, x->m - y->m);
}
return x->p >= y->p;
}
void add(int m, int c, int idx) {
auto it = insert({m, c, 0, idx}) , next = it++, prev = next;
while (isect(next, it)){
it = erase(it);
}
if (prev != begin() && isect(--prev, next)){
isect(prev, next = erase(next));
}
while ((next = prev) != begin() && (--prev)->p >= next->p){
isect(prev, erase(next));
}
}
pair<int,int> query(int x) {
auto l = *lower_bound(x);
return {l.m * x + l.c,l.pos};
}
};
signed main(){
fastio; //judge();
int n,k; cin >> n >> k;
k++;
vector<int>a(n);
for(auto &x : a) cin >> x;
int sum = accumulate(a.begin(),a.end(),0);
vector<int>dp1(n);
vector<vector<int>>pos(n,vector<int>(k+1,-1));
vector<int>pref(n);
int curr = 0;
for(int i = 0;i<n;i++){
curr += a[i];
dp1[i] = curr*curr;
pos[i][1] = 0;
pref[i] = curr;
}
vector<int>dp2(n);
for(int kx = 2;kx<=k;kx++){
LineContainer cht;
for(int i = kx-2;i<=kx-2;i++){
cht.add(2*pref[i],-1*(pref[i]*pref[i] + dp1[i]),i);
}
for(int i = kx-1;i<n;i++){
curr = a[i];
pair<int,int>tmp = cht.query(pref[i]);
dp2[i] = pref[i]*pref[i] - 1*tmp.first;
pos[i][kx] = tmp.second;
cht.add(2 * pref[i], -1 * (pref[i] * pref[i] + dp1[i]), i);
}
dp1 = dp2;
}
cout << (sum*sum - dp1[n-1])/2 << endl;
int num = n-1;
vector<int>ordering;
for(int i = k;i>=2;i--){
ordering.pb(pos[num][i]+1);
num = pos[num][i];
}
reverse(ordering.begin(),ordering.end());
for(auto x : ordering)
cout << x << ' ';
}
