#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, m, a[100005];
ll dp[3][100005];
int cont[205][100005];
deque<pll> dq;
deque<ll> prv;
void insert(pll line) {
while (dq.size()) {
if (dq.front().first == line.first && dq.front().second <= line.second) {dq.pop_front(); prv.pop_front();}
else if (dq.size() >= 2 && (dq[1].second - line.second)*(line.first - dq[0].first) >= (dq[0].second - line.second)*(line.first - dq[1].first)) {dq.pop_front(); prv.pop_front();}
else break;
}
dq.push_front(line);
}
ll qu(ll x) {
if (!dq.size()) return 0;
while (dq.size() >= 2) {
pll tmp = dq.back();
dq.pop_back();
if (dq.back().first * x + dq.back().second < tmp.first * x + tmp.second) {dq.push_back(tmp); break;}
prv.pop_back();
}
return dq.back().first * x + dq.back().second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
iloop(0, n) cin >> a[i];
// gna do without cht first
ll pf[n+1];
pf[0] = 0;
iloop(0, n) pf[i+1] = pf[i] + a[i];
memset(dp, 0, sizeof(dp));
iloop(1, m+1) {
jloop(1, n+1) {
//cout << "dp " << i << " " << j << ":\n";
//cout << "querying " << pf[j] << "\n";
dp[1][j] = qu(pf[j]);
//cout << "res " << dp[i][j] << "\n";
cont[i][j] = (prv.size() ? prv.back() : -1);
insert({pf[j], dp[0][j] - pf[j] * pf[j]});
//cout << "insert " << pf[j] << " " << dp[i-1][j] - pf[j] * pf[j] << " as " << j << "\n";
prv.push_front(j);
}
dq.clear();
prv.clear();
swap(dp[0], dp[1]);
}
cout << dp[0][n] << "\n";
ll ct = n;
iloop(m, 0) {
ct = cont[i][ct];
cout << ct << " ";
}
//cout << "\n";
//iloop(1, m+1) {jloop(1, n+1) {cout << cont[i][j] << " ";} cout << "\n";}
}
