#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
ll a[maxn], par[maxn], dp[maxn];
int m[210][maxn];
struct line{
ll a; // shib
ll b; // arz az mabda
int idx;
line(ll a_ = 0, ll b_ = 0, int idx_ = 1){
a = a_, b = b_, idx = idx_;
}
ll gety(ll x){
return a * x + b;
}
};
stack<line> Q;
bool isgood(line fi, line se, line th){
// return 1ll * (se.b - fi.b) * (fi.a - th.a) < 1ll * (th.b - fi.b) * (fi.a - se.a);
return 1. * (se.b - fi.b) / (fi.a - se.a) < 1. * (th.b - fi.b) / (fi.a - th.a);
}
bool parallel(line fi, line se){
return fi.a == se.a;
}
void add(ll a, ll b, int idx){ // y = ax + b
line nw = line(a, b, idx);
if (!Q.empty() and parallel(nw, Q.top())){
if (b > Q.top().b)
Q.pop();
else
return;
}
while (Q.size() > 1){
line nex = Q.top();
Q.pop();
line other = Q.top();
if (isgood(other, nex, nw)){
Q.push(nex);
break;
}
}
Q.push(nw);
}
pair<ll, int> get(ll x, int idx){
while (!Q.empty() and Q.top().idx >= idx)
Q.pop();
if (Q.empty())
return {-inf, 0};
while (Q.size() > 1){
line nw = Q.top();
Q.pop();
if (nw.gety(x) > Q.top().gety(x)){
Q.push(nw);
break;
}
}
// cout << x << " -> " << Q.top().a << " " << Q.front().b << " " << Q.front().idx << endl;
return {Q.top().gety(x), Q.top().idx};
}
void vitex(){
while (!Q.empty())
Q.pop();
}
int main(){
ios_base::sync_with_stdio (false);
int n, k;
cin >> n >> k;
k ++;
for (int i = 1; i <= n; i++){
cin >> a[i];
par[i] = par[i - 1] + a[i];
}
for (int i = 1; i <= k; i++){
for (int j = n; j >= 1; j--){
if (i == 1){
dp[j] = 0;
continue;
}
auto it = get(par[j], j);
dp[j] = it.first;
m[i][j] = it.second;
}
vitex();
for (int j = 1; j <= n; j++)
add(par[j], dp[j] - par[j] * par[j], j);
}
cout << dp[n] << endl;
int p = k, q = n;
while (p > 1){
if (m[p][q] == 0)
m[p][q] = q - 1;
cout << m[p][q] << " ";
q = m[p][q];
p --;
}
cout << endl;
return 0;
}
