#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,
tree_order_statistics_node_update>;
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()
struct Line{
mutable ll m,c,p, ind;
bool operator<(const Line &o)const{return m<o.m;}
bool operator<(ll x)const{return p<x;}
};
struct CHT : multiset<Line,less<>>{
static const ll inf = LLONG_MAX;
ll div(ll a, ll b){
return a/b - ((a^b)<0 && a%b);
}
bool isect(iterator x, iterator y){
if(y==end()) return x->p=inf,0;
if(x->m==y->m) x->p = x->c > y->c ? inf : -inf;
else x->p = div(x->c - y->c, y->m - x->m);
return x->p>=y->p;
}
void add(ll m, ll c, ll ind){
m = -m, c = -c;
auto z = insert({m,c,0,ind}), y = z++, x = y;
while(isect(y,z)) z = erase(z);
if(x != begin() && isect(--x,y)) isect(x,y=erase(y));
while((y=x) != begin() && (--x)->p >= y->p)
isect(x,erase(y));
}
pair<ll,ll> get(ll x){
assert(!empty());
auto l = *lower_bound(x);
return {-(l.m * x + l.c),l.ind};
}
};
const int mxn = 1e5+10;
const ll inf = 1e17;
ll arr[mxn];
int suc[mxn][201];
void solve(){
int n,k; cin >> n >> k;
CHT cht[k];
for(int i = 1; i <= n; i++){
cin >> arr[i]; arr[i] += arr[i-1];
}
for(int i = 1; i < k; i++) cht[i].add(0,inf,-1);
cht[0].add(-2*arr[1],2*arr[1]*arr[1],1);
ll ans = 0;
for(int i = 2; i <= n; i++){
for(int j = min(i,k); j >= 1; j--){
auto [val,ind] = cht[j-1].get(arr[i]);
ll tmp = val + arr[i]*arr[i];
if(i==n && j==k) ans = tmp;
suc[i][j] = ind;
if(j!=k) cht[j].add(-2*arr[i],arr[i]*arr[i] + tmp,i);
}
cht[0].add(-2*arr[i],2*arr[i]*arr[i],i);
}
cout << (arr[n]*arr[n] - ans)/2 << '\n';
vector<int> res;
for(int u = suc[n][k], cnt = k; cnt>0; u = suc[u][--cnt])
res.pb(u);
reverse(all(res));
for(auto x : res) cout << x << ' ';
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t = 1;
while(t--) solve();
}
