#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define int long long
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e3+3;
const int MOD = 1e9+7;
const bool I = 1;
int n, k, pref[N], a[N];
int get(int l, int r){
if(l - 1 < 0) return pref[r];
return pref[r] - pref[l-1];
}
int dp[N][N];
int par[N][N];
void getfast(int res = -1){
dp[1][1] = get(1, 1) * get(2, n);
for(int p = 1; p <= k; ++p){
for(int i = 1; i < n; ++i){
// if(i == 1 && p == 1) continue;
int ans = -1;
for(int j = 0; j < i; ++j){
int cur = (dp[p-1][j] + get(j + 1, i) * get(i + 1, n));
if(ans <= cur){
ans = cur;
par[p][i] = j;
}
}
dp[p][i] = ans;
}
}
int pos = -1;
vector<int> r;
for(int i = 1; i < n; ++i){
if(res <= dp[k][i]){
res = dp[k][i];
pos = i;
}
}
if(pos != -1){
for(int p = k; p >= 1; --p){
r.pb(pos);
pos = par[p][pos];
}
}
reverse(all(r));
cout << res << '\n';
for(auto it : r){
cout << it << ' ';
}
}
signed main(){
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
pref[i] = pref[i-1] + a[i];
}
getfast();
}
/*
7 3
4 1 3 4 0 2 3
*/
