#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
// struct Line {
// mutable ll k, m, p, num;
// bool operator<(const Line& o) const { return k < o.k; }
// bool operator<(ll x) const { return p < x; }
// };
// struct LineContainer : multiset<Line, less<>> {
// static const ll inf = LLONG_MAX;
// ll div(ll a, ll b) {
// return a / b - ((a ^ b) < 0 && a % b); }
// bool isect(iterator x, iterator y) {
// if (y == end()) return x->p = inf, 0;
// if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
// else x->p = div(y->m - x->m, x->k - y->k);
// return x->p >= y->p;
// }
// void add(ll k, ll m, int i) {
// auto z = insert({k, m, 0, i}), y = z++, x = y;
// while (isect(y, z)) z = erase(z);
// if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
// while ((y = x) != begin() && (--x)->p >= y->p)
// isect(x, erase(y));
// }
// pair<ll, ll> query(ll x) {
// assert(!empty());
// auto l = *lower_bound(x);
// return {l.k * x + l.m, l.num};
// }
// };
namespace geo {
const double EPS = 1e-9;
template <typename T> class point {
static_assert(is_arithmetic<T>::value, "T must be an arithmetic type");
public:
T x, y;
int ind;
point() : x(T{}), y(T{}), ind(0) {}
point(const T &_x, const T &_y) : x(_x), y(_y) {}
point(const T &_x, const T &_y, const int &_i) : x(_x), y(_y), ind(_i) {}
template <typename S> operator point<S>() const {
return point<S>(static_cast<S>(x), static_cast<S>(y));
}
template <typename S> point &operator=(const point<S> &p) {
x = p.x;
y = p.y;
return *this;
}
point &operator+=(const point &p) {
x += p.x;
y += p.y;
return *this;
}
point &operator-=(const point &p) {
x -= p.x;
y -= p.y;
return *this;
}
point &operator*=(const T &s) {
x *= s;
y *= s;
return *this;
}
void swap(point &p) {
swap(x, p.x);
swap(y, p.y);
}
};
template <typename T> point<T> make_point(const T &x, const T &y) {
return point<T>(x, y);
}
template <typename T> void swap(point<T> &p, point<T> &q) { p.swap(q); }
template <typename T> point<T> operator-(const point<T> &p) {
return point<T>(-p.x, -p.y);
}
template <typename T> point<T> operator+(point<T> p, const point<T> &q) {
return p += q;
}
template <typename T> point<T> operator-(point<T> p, const point<T> &q) {
return p -= q;
}
template <typename T> point<T> operator*(point<T> p, const T &s) { return p *= s; }
template <typename T> point<T> operator*(const T &s, point<T> p) { return p *= s; }
template <typename T> T cross(const point<T> &p, const point<T> &q) {
long double ret = (long double)p.x * q.y - (long double)p.y * q.x;
if (abs(ret) > 1e18) return ret > 0 ? 1 : -1;
return p.x * q.y - p.y * q.x;
}
template <typename T> T operator^(const point<T> &p, const point<T> &q) {
return cross(p, q);
}
template <typename T> bool operator==(const point<T> &p, const point<T> &q) {
if constexpr (is_integral<T>::value) return p.x == q.x && p.y == q.y;
else return abs(p.x - q.x) <= EPS && abs(p.y - q.y) <= EPS;
}
template <typename T> bool operator!=(const point<T> &p, const point<T> &q) {
return !(p == q);
}
template <typename T> bool operator<(const point<T> &p, const point<T> &q) {
return p.x < q.x || (p.x == q.x && p.y < q.y);
}
template <typename T> bool operator>(const point<T> &p, const point<T> &q) {
return q < p;
}
template <typename T> bool operator<=(const point<T> &p, const point<T> &q) {
return !(p > q);
}
template <typename T> bool operator>=(const point<T> &p, const point<T> &q) {
return !(p < q);
}
} // namespace geo
struct monotonic_dp_hull {
long long prev_x = LLONG_MIN, prev_y = 1;
deque<geo::point<long long>> points;
void add(const geo::point<long long> &p) {
assert(points.empty() || p.x >= points.back().x);
if (!points.empty() && p.x == points.back().x) {
if (p.y <= points.back().y) return;
points.pop_back();
}
while (size() >= 2 &&
((points.back() - p) ^ (points[size() - 2] - points.back())) <= 0)
points.pop_back();
points.push_back(p);
}
void add(long long m, long long b, int ind) { add(geo::point(m, b, ind)); }
pair<long long, int> query(long long x, long long y = 1) {
assert(size() > 0);
assert(prev_x == LLONG_MIN || x * prev_y >= prev_x * y);
prev_x = x, prev_y = y;
while (size() >= 2 &&
x * (points[1].x - points[0].x) >= (points[0].y - points[1].y) * y)
points.pop_front();
return {points[0].x * x + points[0].y * y, points[0].ind};
}
void clear() {
points.clear();
prev_x = LLONG_MIN, prev_y = 1;
}
int size() const { return points.size(); }
};
int main()
{
// ifstream cin("input.txt");
// ofstream cout("output.txt");
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k; cin >> n >> k;
vector<ll> a(n + 1), p(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
vector<ll> dp(n + 1, 0), ndp(n + 1, 0);
vector<vector<ll>> opt(k + 1, vector<ll>(n + 1));
for (int ki = 1; ki <= k; ki++) {
monotonic_dp_hull cht;
cht.add(p[ki], dp[ki] - p[ki] * p[ki], ki);
for (int i = ki + 1; i <= n; i++) {
auto [v, ind] = cht.query(p[i]);
ndp[i] = v;
opt[ki][i] = ind;
cht.add(p[i], dp[i] - p[i] * p[i], i);
}
swap(dp, ndp);
}
cout << dp[n] << '\n';
int cur = n, ki = k;
while(ki) {
if (opt[ki][cur]) cout << opt[ki][cur] << ' ';
cur = opt[ki--][cur];
}
}
