#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MODULO = 12;
template<class X , class Y>
bool Maximize(X &x , Y y)
{
if(x < y)
{
x = y;
return true;
}
return false;
}
template<class X ,class Y>
bool Minimize(X &x , Y y)
{
if(x > y)
{
x = y;
return true;
}
return false;
}
template<class X ,class Y>
void Add(X &x , Y y)
{
x += y;
if(x >= MODULO) x-= MODULO;
}
template<class X ,class Y>
void Sub(X & x , Y y)
{
x -= y;
if(x < 0 ) x += MODULO;
}
const int N = 1e5+1;
long long dp[2][N];
long long a[N];
int P[201][N];
long long cost(int l ,int r)
{
assert(l <= r);
return (a[r] - a[l-1]) * (a[r] - a[l-1]);
}
void conq(int l ,int r ,int opt_l , int opt_r , bool cur , int k)
{
if(l > r)return ;
int mid = (l+r) >> 1;
dp[cur][mid] = (1ll << 61);
int opt;
for(int i = opt_l ; i <=min(mid -1 , opt_r) ; i++)
{
long long sta = dp[!cur][i] + cost(i +1 , mid);
if(Minimize(dp[cur][mid] , sta))
{
opt = i;
}
}
P[k][mid] = opt;
conq(l , mid-1 , opt_l , opt , cur , k);
conq(mid+1 , r , opt , opt_r , cur , k );
}
vector<int>List;
void trace(int k , int i)
{
if(k == 0)
{
return ;
}
trace(k-1 , P[k][i] );
cout << P[k][i] << ' ';
}
int n ;
int k;
void Input()
{
cin >> n >> k;
for(int i = 1; i <= n ; i++)
{
cin >> a[i];
a[i] += a[i-1];
}
}
void Process()
{
bool cur = false;
for(int i = 1 ; i <= n ; i++)
{
dp[cur][i] = cost(1 , i);
}
for(int g = 1 ; g <= k ; g++)
{
cur ^= 1;
conq(g +1 , n , g , n , cur , g );
}
cout << (cost(1 , n ) - dp[cur][n]) /2LL <<'\n';
trace(k , n);
}
int main()
{
ios_base :: sync_with_stdio(0);cin.tie(0);
int test = 1;
while(test--)
{
Input();
Process();
cout <<'\n';
}
return 0;
}
