//
// main.cpp
// IntensiveCamp 1 2026
//
// Created by Ali AlSalman on 27/04/2026.
//
#include <bits/stdc++.h>
//#define INTERACTIVE
//#define TESTCASES
//#define SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__
#ifndef INTERACTIVE
#define endl '\n'
#endif
template<typename T>
using vec = std::vector<T>;
using namespace std;
vec<long long> arr, P;
map<array<int, 3>, long long> c;
map<array<int, 3>, array<int, 2>> con;
array<int, 3> a(int a, int b, int c) { return {a, b, c}; }
long long ans(int l, int r, int k) {
if (k == 0) {
return 0;
}
if (l == r) { return INT32_MIN; }
if (c.find({l, r, k}) != c.end()) {
return c[a(l, r, k)];
}
long long lans = 0;
for (int i = l; i < r; i++) {
long long optimal_distribution = 0;
for (int lk = 0; lk < k; lk++) {
long long value = ans(l, i, lk) + ans(i + 1, r, k - lk - 1);
if (optimal_distribution < value) {
optimal_distribution = value;
con[a(l - 1, r - 1, k)][1] = lk;
}
}
long long value = (P[r] - P[i]) * (P[i] - P[l - 1]) + optimal_distribution;
if (lans < value) {
lans = value;
con[a(l, r, k)][0] = i;
}
}
return lans;
}
deque<int> cons(int l, int r, int k) {
if (k == 0) return {};
auto [i, lk] = con[a(l, r, k)];
auto a = cons(l, i, lk);
auto b = cons(i + 1, r, k - lk - 1);
if (a.size() < b.size()) swap(a, b);
for (auto x : b) a.push_back(x);
a.push_front(i);
return a;
}
void solve() {
int n, k;
cin>>n>>k;
arr.resize(n); P.resize(n + 1);
for (auto &a : arr) cin>>a;
for (int i = 1; i <= n; i++)
P[i] = P[i - 1] + arr[i - 1];
cout<<ans(1, n, k)<<endl;
for (auto a : cons(1, n, k)) cout<<a<<" "; cout<<endl;
}
int main() {
#ifndef INTERACTIVE
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
int t = 1;
#ifdef TESTCASES
cin>>t;
#endif
for (int i = t; i--;) {
#if defined(TESTCASES) && defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
cout<<"Case "<<t-i<<":\n";
#elif defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
#warning SPOJ_BULLSCHEI�E__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
#endif
solve();
}
return 0;
}
