#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
int n, k;
ll a[nx], f[nx], g[nx];
ll A(int i)
{
return a[i];
}
ll B(int i)
{
return g[i]-a[i]*a[i];
}
long double inter(int i, int j)
{
return (long double)(B(i)-B(j))/(A(j)-A(i));
}
deque<int> st;
vector<int> ve;
int trace[205][nx];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k;
for(int i = 1; i <= n; i++)
cin>>a[i], a[i]+=a[i-1];
for(int i = 1; i <= n; i++)
g[i]=-inf;
for(int l = 1; l <= k+1; l++)
{
st.clear();
for(int i = 0; i <= n; i++)
{
if(i>0)
{
while(st.size()>1 && ((A(st[0])==A(st[1]) && B(st[0])==B(st[1])) || inter(st[0], st[1])<=a[i]))
st.pop_front();
int j=st.front();
f[i]=A(j)*a[i]+B(j);
trace[l][i]=j;
}
while(st.size()>1 && (A(i)==A(st.back()) || inter(st[st.size()-2], st.back())>=inter(st.back(), i)))
st.pop_back();
st.push_back(i);
}
for(int i = 0; i <= n; i++)
g[i]=f[i];
}
cout<<f[n]<<'\n';
for(int i = k+1; i >= 2; i--)
{
n=trace[i][n];
ve.emplace_back(n);
}
reverse(ve.begin(), ve.end());
for(int x:ve) cout<<x<<' ';
}
