#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast \
ios_base::sync_with_stdio (false); \
cin.tie (NULL); \
cout.tie (NULL)
using namespace std;
ll s[1000000+1];
double intersection(pair <ll,ll> c1, pair <ll,ll> c2)
{
double ret=s[c2.ff];
if(s[c1.ff]==s[c2.ff])
return ret;
else
return max(ret,double(c1.ss-c2.ss+(s[c1.ff]+s[c2.ff])*(s[c1.ff]-s[c2.ff]))/double(s[c1.ff]-s[c2.ff])/2.0);
}
signed main()
{
fast;
// freopen("curling.in","r",stdin);
// freopen("curling.out","w",stdout);
ll n,k;
cin>>n>>k;
k+=1;
ll arr[n+1];
rep(i,1,n)
cin>>arr[i];
s[0]=0;
rep(i,1,n)
s[i]=s[i-1]+arr[i];
deque <pair <ll,ll>> curves; // x,y
vector <ll> dp(n+1);
int to[n+1][k+1];
rep(i,1,n)
{
dp[i]=s[i]*s[i];
to[i][1]=0;
curves.push_back({i,dp[i]});
while(sz(curves)>=3)
{
if(intersection(curves[sz(curves)-3],curves[sz(curves)-2])>=intersection(curves[sz(curves)-3],curves[sz(curves)-1]))
curves.pop_back(), curves.pop_back(), curves.push_back({i,dp[i]});
else
break;
}
}
deque <pair<ll,ll>> newcurves;
rep(j,2,k)
{
// cout<<j<<": "<<endl;
// for(auto x:curves)
// cout<<x.ff<<","<<x.ss<<" ";
// cout<<endl;
rep(i,j,n)
{
while(sz(curves)>=2)
{
if(curves[0].ff<i && curves[1].ff<i && curves[0].ss+(s[i]-s[curves[0].ff])*(s[i]-s[curves[0].ff])>=curves[1].ss+(s[i]-s[curves[1].ff])*(s[i]-s[curves[1].ff]))
curves.pop_front();
else
break;
}
// cout<<i<<" "<<curves[0].ff<<endl;
dp[i]=curves[0].ss+(s[i]-s[curves[0].ff])*(s[i]-s[curves[0].ff]);
to[i][j]=curves[0].ff;
newcurves.push_back({i,dp[i]});
while(sz(newcurves)>=3)
{
if(intersection(newcurves[sz(newcurves)-3],newcurves[sz(newcurves)-2])>=intersection(newcurves[sz(newcurves)-3],newcurves[sz(newcurves)-1]))
newcurves.pop_back(), newcurves.pop_back(), newcurves.push_back({i,dp[i]});
else
break;
}
}
swap(curves,newcurves);
newcurves.clear();
}
cout<<(s[n]*s[n]-dp[n])/2<<endl;
for(ll idx=n,br=k;br>=2;br--)
{
idx=to[idx][br];
cout<<idx<<" ";
}
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
/*
10 4
33 4 74 36 79 90 38 26 27 23
*/
/*
6 3
15 82 14 16 62 27
*/
