#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>
#include <tuple>
typedef std::tuple<int, int, int> tiii;
#define t3 std::make_tuple
static std::vector<int> A;
static std::vector<int> psum;
static std::map<tiii, tiii> DP;
static tiii dp(int s, int l, int k);
static tiii _dp(int s, int l, int k) {
int m1, m1_j, m1_k1;
for (int j=1; j<l; j++) {
int s1 = (psum[s+j] - psum[s]) * (psum[s+l] - psum[s+j]);
int m2, m2_k1;
for (int k1=0; k1<k; k1++) {
int s2 = std::get<0>(dp(s, j, k1)) + std::get<0>(dp(s+j, l-j, k-1-k1));
if (k1 == 0 or s2 > m2) {
m2 = s2;
m2_k1 = k1;
}
}
s1 += m2;
if (j==1 or s1 > m1) {
m1 = s1;
m1_j = j;
m1_k1 = m2_k1;
}
}
return t3(m1, m1_j, m1_k1);
}
static tiii dp(int s, int l, int k) {
if (l <= 1 or k <= 0)
return t3(0, 0, 0);
if (l == 2)
return t3(A[s] * A[s+1], 1, 0);
auto key = t3(s, l, k);
auto it = DP.find(key);
if (it != DP.end())
return it->second;
tiii val = _dp(s, l, k);
DP[key] = val;
return val;
}
static std::vector<int> answer;
static void recover(int s, int l, int k) {
if (l <=1 or k <= 0)
return;
tiii x = dp(s, l, k);
int j = std::get<1>(x);
int k1 = std::get<2>(x);
answer.push_back(s + j);
recover(s, j, k1);
recover(s+j, l-j, k - 1 - k1);
}
int main(int argc, char const *argv[]) {
int n, k;
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 << std::get<0>(dp(0, n, k)) << std::endl;
recover(0, n, k);
for (int a: answer)
std::cout << a << " ";
std::cout << std::endl;
/*
for (auto it = DP.begin(); it != DP.end(); it++)
std::cout << "DP " << std::get<0>(it->first) << ", "
<< std::get<1>(it->first) << ", " << std::get<2>(it->first)
<< " = " << std::get<0>(it->second) << ", "<< std::get<1>(it->second)
<< ", " << std::get<2>(it->second) << '\n';
std::cin >> n;
*/
return 0;
}
