#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct lajn
{
ll k;
ll n;
int idx;
};
#define MAXN 100005
#define MAXK 205
deque <lajn> q;
ll a[MAXN];
ll dp[MAXN][MAXK];
int opt[MAXN][MAXK];
ll f(ll k,ll n,ll x)
{
return k*x+n;
}
bool useless(ll x)
{
lajn a = q.front();
q.pop_front();
lajn b = q.front();
q.push_front(a);
if(f(a.k,a.n,x)<=f(b.k,b.n,x))return true;
return false;
}
void calc(int idx,int n)
{
q.clear();
for(int i = 1; i <= n; i++)
{
while(1)
{
if(q.size()<=1)break;
if(useless(a[i]))q.pop_front();
else break;
}
lajn aa = (q.size() > 0) ? q.front():lajn();
dp[idx][i]=f(aa.k,aa.n,a[i]);
opt[idx][i]=aa.idx;
aa.k=a[i];
aa.n=-a[i]*a[i]+dp[idx-1][i];
aa.idx=i;
q.push_back(aa);
}
}
int 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 i = 1; i <= k; i++)
{
calc(i,n);
}
cout << dp[k][n] << "\n";
int now = n;
while(k > 0)
{
cout << opt[k][now] << " ";
now = opt[k][now];
k--;
}
return 0;
}
