#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ld double
#define maxn 200009
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<ll> vl ;
typedef vector<pii> vii ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow (a,n/2) ;
if ( n % 2 ) return 1ll*res*res%mod*a%mod ;
else return 1ll*res*res%mod ;
}
int n , k ;
int a [maxn] , sum [maxn] ;
ll dp [maxn] ;
int trace [maxn][209] ;
struct line {
int a ; ll b ;
int id ;
line ( int _a , ll _b , int _id ) {
a = _a , b = _b , id = _id ;
}
ll eval ( int x ) {
return 1ll*x*a+b ;
}
};
struct CHT {
vector <line> T ;
bool badline ( line A , line B , line C )
{
return (ld)(C.b-A.b)/(A.a-C.a) <= (ld)(B.b-A.b)/(A.a-B.a) ;
}
void ins ( line m )
{
while (T.size()>=2)
{
if ( badline(T[T.size()-2],T.back(),m)) T.pop_back() ;
else break ;
}
T.pb(m) ;
}
pair<ll,ll> get ( int x )
{
int l = 0 , r =T.size()-2 ;
while ( l <= r )
{
int mid = (l+r)/2 ;
if ( T[mid].eval(x) <= T[mid+1].eval(x) ) l = mid + 1 ;
else r = mid - 1 ;
}
return {T[l].eval(x),T[l].id} ;
}
void clear ()
{
T . clear () ;
}
};
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0) ;
// rf () ;
cin >> n >> k ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i] , sum [i] = sum [i-1] + a [i] ;
k ++ ;
memset ( dp , 0x3f , sizeof dp ) ;
CHT T ;
for ( int r = 1 ; r <= k ; r ++ )
{
T.clear() ;
T.ins({0,0,0}) ;
for ( int i = 1 ; i <= n ; i ++ )
{
int C = sum [n] - sum [i] ;
auto F = T.get (-C) ;
if ( dp[i] < 1e18 ) T.ins({sum[i],dp[i],i}) ;
dp [i] = F.fi + 1ll*C*sum[i] ;
trace [i][r] = F.se ;
}
}
cout << dp [n] << "\n" ;
vi res ;
int pos = n ;
while ( k > 1 )
{
pos = trace [pos][k] ;
res . pb (pos) ;
k -- ;
}
reverse(res.begin(),res.end()) ;
for ( auto x : res ) cout << x << " " ;
}
// range , error , check speical , ...
// find key , find key
//'-std=c++11' stay hard
// there is no tomorrow
