#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>
#include <tuple>
typedef std::tuple<int, int, int> tiii;
typedef std::pair<long long, int> li;
#define t3 std::make_tuple
static std::vector<int> A;
static std::vector<int> psum;
static std::map<tiii, li> DP;
static li dp(int s, int l, int k);
static li _dp(int s, int l, int k) {
long long m = 0;
int m_j = 0;
for (int j=1; j<l; j++) {
long long ans = (psum[s+j] - psum[s]) * (psum[s+l] - psum[s+j])
+ dp(s+j, l-j, k-1).first;
if (j==1 or ans > m) {
m = ans;
m_j = j;
}
}
return {m, m_j};
}
static li dp(int s, int l, int k) {
if (l <= 1 or k <= 0)
return {0LL, 0};
if (l == 2)
return {(long long) A[s] * A[s+1], 1};
auto key = t3(s, l, k);
auto it = DP.find(key);
if (it != DP.end())
return it->second;
li 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;
li x = dp(s, l, k);
int j = x.second;
answer.push_back(s + j);
recover(s+j, l-j, k - 1);
}
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 << dp(0, n, k).first << 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;
}
