#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
const int maxk = 2e2 + 20;
ll dp[maxn] , pd[maxn];
int par[maxn][maxk] , ind , sum[maxn];
inline ll get(int i , int j)
{
if(i <= j)
return 1e18;
return 1LL * (sum[i] - sum[j]) * (sum[i] - sum[j]) + pd[j];
}
inline void solve(int l , int r , int L , int R)
{
if(l > r)
return;
int m = (l + r) / 2 , pt = L;
ll mn = 1e18;
for(int i = L; i <= R && i < m; i++)
if(mn >= get(m , i))
{
mn = get(m , i);
pt = i;
}
par[m][ind] = pt;
dp[m] = get(m , pt);
solve(l , m - 1 , L , pt);
solve(m + 1 , r , pt , R);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n , k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> sum[i] , sum[i] += sum[i - 1];
for(int i = 1; i <= n; i++)
pd[i] = 1e18;
for(int i = 1; i <= k + 1; i++)
{
ind = i;
solve(0 , n , 0 , n);
for(int i = 0; i <= n; i++)
pd[i] = dp[i];
}
cout << (1LL * sum[n] * sum[n] - dp[n]) / 2 << endl;
int A = n;
vector<int> ans;
for(int i = k + 1; i > 1; i--)
{
ans.pb(par[A][i]);
A = par[A][i];
}
reverse(ans.begin() , ans.end());
for(auto x : ans)
cout << x << " ";
cout << endl;
}
