//#include <bits/stdc++.h>
#include <random>
#include "set"
#include <iostream>
#include "vector"
#include "deque"
#include "climits"
#include "algorithm"
#include "stack"
#include "map"
#include "unordered_set"
#include "bitset"
#include "unordered_map"
#include "stack"
#include "queue"
#include "cstring"
using namespace std;
/*
====================================================================================================
#*###*############*####*#####*####*############*#########################################*##########
%%%%%%%%%###%##*##=*+++=+++++++++++++*@#@%%###%%%%%%%%%%%%%%%%%%%%@%@@@%@@@@@@@@@@@@@%%%%%%%@@@%%%%#
%%%%%%%%%%#####*##=*++++++++++++++++=*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%@@@@@@@@%%%@@%%@@@%%%%#
%%%%%%%%%######*##=*+++++++++++++++++*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%@@@@@@@@@%%#%%%%@@%#%#%#
%%%%%%%%%%%####*##=*++++++++++++++++=+@%@%%###%@@@%%%%%%%%%%%%%%%%%%%%%%%@@%%%%@@@@@%%@%%%%%@%%%####
%%%%%%%%%%####%*##=*++++++++++++++++=+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@%@@@%%%%%@%######
%%%%%%%%%%####%*##=*++++++++++++++===+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%@@@@%#@%%%%%%@%#######
%%%%%%%%%%#####*##+++++++++++=++++=+++@%#%##%#######%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@#%%%%%%@########
%%%%%%%%%%#####*##+*+++++++++++++++==@%%%%%@##:-%=-=-+@%%%%%%%%%%%%%%%%%%%%%%%@@%%%@@@%%%%%@%%######
%%%%%%%%%%#####*##+*++++++++++++=+*%%%%%%%%#%*.@:-%+-++%%%%%%%%%%%%%%%%%%%@%%%@%%%%%%%%%%%@@%#######
%%%%%%%%%%####%*##=*=++++++++++++@%%%%%%%%%%%%#@@@@@@@=-@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@#######
%%%%%%%%%%####%*##+*++++++++++++%@%%@%%%%%%%%#%@###*#%%@@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
%%%%%%%%%%####%*##+*+++++++++==@@%@@@@%%@%###%#@#=%@@@@@@@#=+@%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
%%%%%%%%%%####%*##*++++++++++++@@@@@@%#%%%%@#@@@@@@@@@@@@@@@@@-#%%%%%%%%%%%%%%@%%%%%%%%%%@@@%%%#####
%%%%%%%%%#########=*++++++++++@@@@@%#@@@%%@@@@@@@@@@@@@@@@@@@@%@%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%#####
%%%%%%%%######%*##=*++++++++++@%%@@@@@@@@@%%%####%@@%%%%@@@@@@@%#%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%#####
%%%%%%%%##########=*++++++***#%%@@@@@@%%##*++++++***#*++*#%@@@@%%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%####
%%%%%%%%######%###=*++++++#@%%@%@@@@%#*+++++====++++++++++*#@@@@%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%%###
%%%%%%%%######%###=*++++*%%%%@@@@@@@#+++++++=========++++++*#@@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%####
%%%%%%%%%#####%###=*++**%@#@@@@@@@@%+++=================++++*@@@@%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
%%%%%%%%%#########=*+*#*@%@@@@@@%@%*++*+**##*++======*####*#*%@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
%%%%%%%%%%########=#+*@%@@@@@@%@@@#*+=-=****#*+=+++=**#**#*+*#%@@%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###
%%%%%%%%%%########+#*#@@@@%%%@@@%%#*+++*+=##+#*+*++##*+%**#**#%@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
%%%%%%%%%%########=#**@@@@@@@@@@@@#*+=+=+++++++*==+*#*****++*#%%@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
%%%%%%%%%#########=#**@@@@@@@@@@@@#*+===++++==+=+++**++=++++#%@@@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
%%%%%%%%%#####%###=##%@@@@@@@@@@@@#**+========++====++==+++*#%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##
%%%%%%%#%#########+#+%@%#@@@@@@@@@%**+========+++===*++++++#%@@@%@%%%%%%%%@%%%%@%%%%%%%%%%%%%%%%####
%%%%%%%%%%%#######=#+@@@@@@@@@@@@@#**++===+++****#**##*+++*%%@@@@@@%%%%@@@@@@@@@@@%%%%%%%%%%%%%%####
@%%%%%##%%########+***@@@@@@@@@@@%#***++++*****#%###%%****#%@@@@%@%%%%%%%%%%%%%%%%%%%%%%%%#%%%%%%@@@
%%%%%%%#%##%%%%###+**##%#@@@@@@@###***+++++++++++++*******#@@@@@@%%#%%%%%%%%%%%@%%%%%%%%%%%%%%%%%##%
#@##%%##%##%######+**+++*@%##%%%%*********+++++++**********@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##%
%@##%#%%%####%####+#*+*+++++++++#%**************************#%#*#%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%#%%%#
@%%###%#%########*++===========++#@*++******##########******#++======@%%%%%%%%@%%%%%%%%%%%%%%%%%#%%#
%%%##%##%##%###*++=========+=++++++*#********######*******+*=+==--=====*%%%#%%@%%%%%%%%%%%%%%%@%%%%#
%%%##%%#%#####+++++*+=========+==+++**#******#####*******+*+++++==:======*%#%%@%%%%%%%%%%%%%%%%%%%#%
%%%##%%%%#++==========--=----====+++++*##*****###*****+++#*===--+=====-------+**#@@%%%%%%%%%%%%%%%%%
%#%%%+*++==========-=--=---------========++*@********+=%#===========----------======+@%%%%%%%%%%%%%%
%#%***++========----------------------======++@.+++++*+==========---------------=-=====@%%%%%%%%%%%%
%%**+++=========------------=---------=======+++*+*+%++========------------------==-====%%%%%%%%%%%%
%**++++=========--===-=--=======------===========#*++============---------====----======+*%%%%%%%%%%
#**+++++====+============+++++========-===========+*==============--=====+++++=====+===+=+*%%%%%%%%%
#****+++==++++=====++++++****+++++===--=========+++++++=================+++***+++++++++++++%%%%%%%%%
#*****+++++++++++++++++***##***++===-=---=======++*=*++++==============++++**#***+++++++++*+%%%%%%%%
#******++++***++++++***######*+=====-----=--====++*+**+++======-=--=======+*#*##***+*+****#+@@%%%%%%
##********+**********####%%%+++++=====-----=====++*+***+++================++*#%####*********%@%+%%%%
###***************######%%#**++++++=============++++*#*+++======-========++++*%%####******#*%@@%%%%%
####****************##%%@#***++++++++++=========+++*=**++==============++++++**%%###*********#%%*%%%
*****************+====*%%*********+++++===+====+++++++**++==+=*=====+++++++****@##++++=+****++*@%%%%
*************+++=====--=@************+++++++++++++++******+++++++++++++++******#*+=====+++++*+++@%%%
***+++++*++++++=========+########**#%%*******++******%##***+++*++++++++++*******++++====++=++++**%%%
***+++========++========+%######*%###%#**************%###***************########***++++++++++++**#%%
***+++++++=====+++====+++*@#####%%%%%%######********#######**********###%%%%##%#**#*+++++==+++++**%%
***++++++++=======++++++**@%#######################%*#%%%#################%%#%%##**#*+++++++++++***%
***+++++**+++==========+*+#%%#######################**#%%###################%@%###*##*++++*+++++***%
****+**+++++++=======++*#*#@%%%%%%%%###########%%%#*****##%#%###########%%%%@%%%######+++++++++++***
#*****+++++++++=====+++***#%%%%%%%%%%%%%%%%%%%%%%**++===+*#%%%%%%%%%%%%%%%%%@@%%#######*++++===+++**
#*****+++++++=======+++**#%%%%%%%##############*+++==-===++*####%%%%%%##%%%%@@%%%######**+=====+++**
##****+++++++=====+*++***#%%%%%%%###########***++++++++++=++**############%%%%%%%%####****#*+=++++**
====================================================================================================
*/
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>
#define _ << ' ' <<
#define clearvis for (int i=0; i<maxn;visited[i++]=false)
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
ll fastpow(ll base, ll exp) {
ll res = 1;
while (exp) {
if (exp & 1)
res *= base;
base *= base;
res %= MOD;
base %= MOD;
exp >>= 1;
}
return res;
}
//__int128 fpow(ll base,ll exp){__int128 result=1;while (exp){if (exp%2==1) result*=base;exp/=2;base*=base;}return result;}
void solve() {
srand(time(0));
ll n,k; cin >> n >> k;
ll arr[n+2], pref[n+2];
set<ll> splits = {0, n};
pref[0] = 0;
for (int i=1; i<=n; i++){
cin >> arr[i];
pref[i] = arr[i] + pref[i-1];
}
pref[n+1] = pref[n];
ll ans = 0;
vll ansv;
while (k--){
ll bestans=0;
ll besti=0;
for (int i=1; i<=n; i++){
if (splits.count(i)) continue;
auto L = splits.lower_bound(i); L--;
auto R = splits.upper_bound(i);
ll curans = 1;
curans *= pref[*R] - pref[i];
curans *= pref[i] - pref[*L];
if (curans >= bestans){
if (curans == bestans) if (rand() % 3 == 2) continue;
bestans = curans;
besti = i;
}
}
pb(ansv, besti);
ans += bestans;
splits.insert(besti);
}
// cout << endl;
cout << ans << endl;
for (ll x : ansv) cout << x << ' ';
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
//freopen("berries.in","r",stdin);
//freopen("berries.out","w",stdout);
ll t=1;
// cin >> t;
for (int i=1; i<=t; i++){
//cout << "Case #" << i << ": ";
solve();
cout << endl;
}
return 0; // code
}
