#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define ll long long
#define _sz(e) e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC target("sse4,avx,avx2")
#pragma GCC optimize("O3,unroll-loops")
const ll maxn = 1e5 + 8 , N = 200 + 8 , mod = 1e9 + 7 , INF = 1e18;
int n , k , par[maxn][N];
ll dp[2][maxn] , ps[maxn] , a[maxn];
void get(int l , int r , int ql , int qr , int K) {
if(r - l < 1 || qr - ql < 1) return ;
bool b = (K & 1);
int mid = (l + r) / 2;
dp[b][mid] = INF;
for (int i = ql; i < min(qr , mid); ++i) {
ll val = dp[b ^ 1][i] + (ps[mid + 1] - ps[i + 1]) * (ps[mid + 1] - ps[i + 1]);
if(val < dp[b][mid]) {
par[mid][K] = i , dp[b][mid] = val;
}
}
get(l , mid , ql , par[mid][K] + 1 , K);
get(mid + 1 , r , par[mid][K] , qr , K);
}
int main() {
FAST;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
ps[i + 1] = ps[i] + a[i];
dp[1][i] = ps[i + 1] * ps[i + 1];
par[i][1] = -1;
}
for (int i = 2; i <= k + 1; ++i) {
get(0 , n , 0 , n , i);
}
int b = (k + 1) & 1;
cout << ((ps[n] * ps[n]) - dp[b][n - 1]) / 2 << '\n';
int c_id = n - 1 , c_k = k + 1;
while(c_k > 0 && par[c_id][c_k] != -1) {
cout << par[c_id][c_k] + 1 << ' ';
c_id = par[c_id][c_k];
c_k--;
}
cout << '\n';
}
