#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+1;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const ll inf=1e18;
const int K=600;
ll dp[mxN], dp2[mxN], a[mxN], p[mxN];
ll cost(int l, int r)
{
if(l>r) return 0;
return (p[r]-p[l])*(p[r]-p[l]);
}
int pos[200][mxN];
void solve(int l, int r, int optl, int optr, int layer)
{
if(l>r) return;
int m=(l+r)/2, opt=m-1;
ll best=dp[m];
for(int k=optl; k<=min(m-1,optr); k++)
{
ll cur=dp[k]+cost(k,m);
if(cur<=best)
{
best=cur;
opt=k;
}
}
dp2[m]=best;
pos[layer][m]=opt;
solve(l,m-1,optl,opt,layer);
solve(m+1,r,opt,optr,layer);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) p[i]=a[i]+p[i-1];
for(int i=1; i<=n; i++) dp[i]=p[i]*p[i];
for(int i=0; i<k; i++)
{
solve(1,n,1,n,i);
for(int i=1; i<=n; i++) dp[i]=dp2[i];
}
cout << (p[n]*p[n]-dp[n])/2 << "\n";
vector<int> ans;
int x=n;
while(~--k)
{
ans.push_back(pos[k][x]);
x=pos[k][x];
}
reverse(ans.begin(),ans.end());
for(int i:ans) cout << i << " ";
cout << "\n";
}
/*
7 3
4 1 3 4 0 2 3
*/
