#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
const int BLN = 5;
int x, k;
int arr[100005];
int pfx[100005];
int64_t dp[100005][2];
int last[100005][205];
inline int sum_query(int l, int r) {
return pfx[r] - pfx[l-1];
}
void dnc(int lvl, int l, int r, int optl, int optr) {
if (l>r) {
return;
}
int m = (l+r)>>1;
std::pair<int64_t,int> opt(-0x3f3f3f3f3f3f3f3f,-0x3f3f3f3f);
for (int i = std::max(0, optl-BLN); i < std::min(m, optr+1+BLN); i++) {
opt = std::max(opt,std::pair<int64_t,int>(1LL*sum_query(i+1,m)*sum_query(m+1,x)+dp[i][(lvl-1)&1], i));
}
dp[m][lvl&1] = opt.first;
last[m][lvl] = opt.second;
dnc(lvl,l,m-1,optl,opt.second);
dnc(lvl,m+1,r,opt.second,optr);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> k;
for (int i = 1; i <= x; i++) {
std::cin >> arr[i];
pfx[i] = pfx[i-1] + arr[i];
}
++k;
for (int i = 1; i <= k; i++) {
dnc(i,1,x,1,x);
}
std::cout << dp[x][k&1] << "\n";
int i = x, j = k;
std::vector<int> stk;
while (j) {
if (i!=x) stk.emplace_back(i);
i = last[i][j];
--j;
}
int last = 0;
while (!stk.empty()) {
std::cout << stk.back() << " ";
stk.pop_back();
}
std::cout << "\n";
}
