//srand(time(0)) - always changing
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;
int gcd(int a, int b) {
while (b) {
a %= b;
swap (a, b);
}
return a;
}
ll __sqrt(ll x) {
ll result = 0;
for (ll k = 1ll << 30; k != 0; k >>= 1) {
if ((result + k) * (result + k) <= x) {
result += k;
}
}
return result;
}
int a[1010], p[1010], dp[1010][1010][2];
int sum(int l, int r) {
return p[r] - p[l - 1];
}
void GazizMadi() {
int n, m, ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
for (int i = 1; i < n; i++) {
for (int k = 1; k <= min(i, m); k++) {
for (int j = 1; j <= i; j++) {
if (dp[i][k][0] <= dp[j - 1][k - 1][0] + sum(j, i) * sum(i + 1, n)) {
dp[i][k][0] = dp[j - 1][k - 1][0] + sum(j, i) * sum(i + 1, n);
dp[i][k][1] = j;
}
}
// cout << i << ' ' << k << ' ' << dp[i][k][0] << '\n';
}
if (dp[ans][m][0] <= dp[i][m][0]) {
ans = i;
}
}
cout << dp[ans][m][0] << '\n';
vector <int> act;
while (m--) {
act.pb(ans);
ans = dp[ans][m][1];
}
reverse(all(act));
for (int it: act) {
cout << it << ' ';
}
}
const bool Cases = 0;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TT = 1;
if (Cases) cin >> TT;
for (int i = 1; i <= TT; i++) {
//cout << "Case " << i << ": ";
GazizMadi();
}
}
