#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>
#include <algorithm>
#include <list>
static std::vector<int> A;
static std::vector<int> psum;
static int n, k;
static std::vector<std::vector<int>> offset; // (k+1) x (n+1) -> offset
static std::list<int> answer;
static long long dp(void) {
if (n <= 1)
return 0LL;
int k1;
for (k1=0; k1<=k; k1++)
offset.push_back(std::vector<int> (n+1, 0));
std::vector<long long> prevrow(n+1, 0);
std::vector<long long> row(n+1, 0);
// k = 0 => all offsets are zero
for (k1=1; k1<=k; k1++) {
std::swap(row, prevrow);
for (int i=2; i<=(k1+1); i++) {
row[i] = prevrow[i-1] + psum[i-1] * A[i-1];
offset[k1][i] = i-1;
}
for (int i=(k1+2); i<=n; i++) {
int last = offset[k1][i-1];
int next = last + 1;
long long val1 = prevrow[last] + psum[last] * (psum[i] - psum[last]);
long long val2 = 0LL;
while (next < i) {
val2 = prevrow[next] + psum[next] * (psum[i] - psum[next]);
if (val1 > val2)
break;
val1 = val2;
next ++;
}
row[i] = val1;
offset[k1][i] = next - 1;
}
}
int lastoffset = n;
k1 = k;
while (k1 > 0) {
lastoffset = offset[k1][lastoffset];
answer.push_front(lastoffset);
k1 --;
}
return row[n];
}
int main(int argc, char const *argv[]) {
std::cin >> n >> k;
for (int i=0; i<n; i++) {
int a;
std::cin >> a;
A.push_back(a);
}
psum.push_back(0);
for (int i=0; i<n; i++)
psum.push_back(A[i] + psum[i]);
std::cout << dp() << std::endl;
for (int a: answer)
std::cout << a << " ";
std::cout << std::endl;
return 0;
}
