#include<bits/stdc++.h> using namespace std; #define ll long long #define co cout<< // stuff const int maxn=1e4+5,maxk=205; ll dp[maxn][maxk],arr[maxn],pref[maxn]={},pos[maxn][maxk]; ll n,k; ll rec(ll x,ll left){ if(left==0) return 0; if(x==n) return -1e18; if(dp[x][left]!=-1) return dp[x][left]; ll mx=-1e18,ps; for(int y=x+1;y<=n;y++){ ll a=rec(y,left-1)+(pref[n]-pref[y-1])*(pref[y-1]-pref[x-1]); if(a>mx) mx=a,ps=y-1; } pos[x][left]=ps; return dp[x][left]=mx; } void solve(){ memset(dp,-1,sizeof(dp)); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>arr[i]; pref[i]=pref[i-1]+arr[i]; } co rec(1,k)<<'\n'; ll a=1; while(k){ co pos[a][k]<<' '; a=pos[a][k]+1,k--; } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int _=1; //cin>>_; while(_--) solve(); }