#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 7 ;
struct Line {
mutable ll k , m , p , id ;
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 id ) {
auto z = insert ( { k , m , 0 , id } ) , 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 , int > query ( ll x ) {
assert ( !empty ( ) ) ;
auto l = *lower_bound ( x ) ;
return { l.k * x + l.m , l.id } ;
}
};
int n , k ;
int a[ MAXN ] ;
ll pref[ MAXN ] ;
ll dp[ 2 ][ MAXN ] ;
int hh[ 202 ][ MAXN ] ;
void solve ( ) {
cin >> n >> k ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ] ;
pref[ i ] = pref[ i - 1 ] + a[ i ] ;
}
int prv = 0 , nxt = 1 ;
for ( int lvl = 2 ; lvl <= k + 1 ; ++ lvl ) {
LineContainer w ;
w.add ( pref[ lvl - 1 ] , dp[ prv ][ lvl - 1 ] - pref[ lvl - 1 ] * pref[ lvl - 1 ] , lvl - 1 ) ;
for ( int i = lvl ; i <= n ; ++ i ) {
tie ( dp[ nxt ][ i ] , hh[ lvl ][ i ] ) = w.query ( pref[ i ] ) ;
w.add ( pref[ i ] , dp[ prv ][ i ] - pref[ i ] * pref[ i ] , i ) ;
}
prv ^= 1 , nxt ^= 1 ;
}
cout << dp[ prv ][ n ] << "\n" ;
vector < int > ans ;
int x = n , y = k + 1 ;
while ( y > 1 ) {
ans.push_back ( hh[ y ][ x ] ) ;
x = hh[ y ][ x ] ; -- y ;
}
reverse ( ans.begin ( ) , ans.end ( ) ) ;
for ( auto x : ans ) {
cout << x << " " ;
}
cout << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
