//這世界上沒有什麼是永恆不變的，只有我和我的自我
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ii int
#define pb push_back
#define fi first
#define se second
#define Op operator
#define bp __builtin_popcount
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define nn cout<<"NO"<<endl;
#define yy cout<<"YES"<<endl;
#define rep() for(ll i=1 ; i<=n ; i++) cin>>a[i];
#define End() for(ll i=1 ; i<=n ; i++) cout<<a[i]<<" ";
#define TT ll tt;cin>>tt;while(tt--){Test_Case();}
#define T Test_Case() ;
using namespace std;
const ii N = 1e5 , M = 1e6 , mod = 1e9 + 7 , Ones = 1 , Zero = 0;
const ll oo = 1e18 ;
ii a[N + 5] , trace[N + 5][205] ;
ll dp[N + 5][2] , Pre[N + 5] ;
void Calc(ii l , ii r , ii x , ii y , ii k) {
if(l > r) return ;
ii mid = l + r >> 1 , op = 0 ;
for(ii i = x ; i <= min(y , mid - 1) ; i ++ ) {
if(dp[mid][1] <= Pre[i] * (Pre[mid] - Pre[i]) + dp[i][0]) {
dp[mid][1] = Pre[i] * (Pre[mid] - Pre[i]) + dp[i][0]; op = i ;
}
}
trace[mid][k] = op ;
Calc(l , mid - 1 , x , op , k) ; Calc(mid + 1 , r , op , y , k) ;
}
void Test_Case(){
ii n , k ; cin >> n >> k ;
for(ii i = 1 ; i <= n ; i ++) {
cin >> a[i] ; Pre[i] = Pre[i - 1] + a[i] ;
}
for(ii i = 1 ; i <= k ; i ++ ) {
for(ii j = 1 ; j <= n ; j ++) {
dp[j][0] = dp[j][1] ; dp[j][1] = 0 ;
}
Calc(1 , n , 1 , n , i ) ;
}
cout << dp[n][1] << endl ;
vector<ii> ans ; ii now = n ;
if(dp[n][1] == 0) {
for(ii i = 1 ; i <= k ; i ++ ) {
cout << i << " " ;
}
return ;
}
while(trace[now][k] > 0) {
ans.pb(trace[now][k]) ; now = trace[now][k -- ] ;
}
reverse(ans.begin() , ans.end()) ;
for(auto & it : ans) cout << it << " " ;
}
int main(){
Faster
//freopen("???.inp", "r", stdin);
//freopen("???.out", "w", stdout);
T ;
}
////////////////////////////////////////////////////////////////////////////////////////
// //
// Coded by SkyZCoder //
// //
////////////////////////////////////////////////////////////////////////////////////////
