#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <unordered_set>
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#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
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(all(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(all(v),x)-v.begin())
const int N = 1e5 + 78 , inf = 1e18 , M = 1e9 + 7;
using namespace std;
string trans(int n , int k){
string s = "";
while(n != 0){
int d = n % k;
if(d < 10){
s = to_string(d) + s;
}
else{
s = char(d + 'A' - 10) + s;
}
n /= k;
}
return s;
}
int pref[N] , suff[N];
int dp[10000][10000];
int p[1000][1000];
void solve(){
int n , k;
cin >> n >> k;
int a[n + 1];
int x = 0;
vector<int> v;
for(int i = 1 ; i <= n ; i++){
cin >> a[i];
p[i][k] = 1;
}
for(int i = 1 ; i <= n ; i++)pref[i] = pref[i - 1] + a[i];
for(int i = n ; i >= 1 ; i--)suff[i] = suff[i + 1] + a[i];
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < i ; j++){
for(int l = 1 ; l <= k; l++){
if( dp[j][l - 1] + (pref[i] - pref[j]) * suff[i + 1] > dp[i][l] + a[i]){
p[i][l] = max(j , 1ll);
}
dp[i][l] = max(dp[i][l] , dp[j][l - 1] + (pref[i] - pref[j]) * suff[i + 1]);
}
}
}
for(int i = 1 ; i <= n ; i++){
if(dp[i][k] > dp[x][k])x = i;
}
cout << dp[x][k] << '\n';
while(p[x][k]){
v.pb(x);
if(x == p[x][k])break;
x = p[x][k--];
}
// v.pb(x);
reverse(all(v));
for(auto it : v)cout << it << ' ';
//for(auto it : g[n - 1][k])cout << it << ' ';
}
signed main(){
Bekabot
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
