#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 10000, MAX_K = 200;
int n, k, s[MAX_N + 1];
pair<int, ll> dp[MAX_K + 1][MAX_N + 1];
struct line{
int m, from;
ll b;
line(){}
line(int _m, ll _b, int _from) :m(_m), b(_b), from(_from){}
}l[MAX_N];
int h, t;
double cross(line l1, line l2){ return (double)(l1.b - l2.b) / (l2.m - l1.m); }
void add(line x){
while (t - h > 1 && cross(l[t - 2], x) > cross(l[t - 1], x)) t--;
l[t++] = x;
}
pair<int, ll> f(int x){
while (t - h > 1 && cross(l[h], l[h + 1]) < x) h++;
return{ l[h].from, (ll)l[h].m*x + l[h].b };
}
int main(){
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++){
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
for (int i = 1; i <= k; i++){
h = t = 0;
add(line(s[i], dp[i - 1][i].second - (ll)s[i] * s[i], i));
for (int j = i + 1; j <= n; j++){
dp[i][j] = f(s[j]);
add(line(s[j], dp[i - 1][j].second - (ll)s[j] * s[j], j));
}
}
printf("%lld\n", dp[k][n].second);
vector<int> v;
for (int i = k, tmp = n; i >= 1; i--){
tmp = dp[i][tmp].first;
v.push_back(tmp);
}
for (int i = v.size() - 1; i >= 0; i--)
printf("%d ", v[i]);
return 0;
}
