#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int N = 1<<17;
int strt[N], dp[N][2], a[N];
signed Par[N][201];
int intersection(int i1, int i2){
int m1 = a[i1], m2 = a[i2], c1 = dp[i1][0] - a[i1] * a[i1], c2 = dp[i2][0] - a[i2] * a[i2];
if (m1 == m2){
if (c1 > c2)
return 2e9;
return -1;
}
int x = (c2 - c1) / (m1 - m2);
while (c1 + x * m1 > c2 + x * m2)
x++;
return x;
}
void solve(int n, int k){
if (k == 0){
cout<<n<<' ';
return;
}
solve(Par[n][k], k - 1);
cout<<n<<' ';
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, K;
cin>>n>>K;
for (int i=1;i<=n;i++)
cin>>a[i], a[i] += a[i-1];
for (int k=1;k<=K;k++){
vector<int> vec;
for (int i=1;i<=n;i++){
int l = 0, r = vec.size();
while (l + 1 < r){
int mid = (l + r) / 2;
if (strt[vec[mid]] <= a[i])
l = mid;
else
r = mid;
}
if (vec.size() > 0){
Par[i][k] = vec[l];
dp[i][1] = dp[vec[l]][0] + a[vec[l]] * (a[i] - a[vec[l]]);
}
while (vec.size() > 0 and intersection(vec.back(), i) <= strt[vec.back()])
vec.pop_back();
if (vec.size() > 0)
strt[i] = intersection(vec.back(), i);
vec.push_back(i);
}
for (int i=1;i<=n;i++)
dp[i][0] = dp[i][1], dp[i][1] = 0;
}
cout<<dp[n][0]<<'\n';
solve(Par[n][K], K - 1);
cout<<'\n';
}
