#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll dp[100002][202];
ll ans[100002][202];
int main(){
ll n,k;
cin >> n >> k;
ll suff[n+1];
vector<ll> nums(n);
FOR(i,0,n) cin >> nums[i];
suff[n] = 0;
suff[n-1] = nums[n-1];
FORNEG(i,n-2,-1){
suff[i] = suff[i+1] + nums[i];
}
dp[0][0] = 0;
FOR(i,0,n){
FOR(j,0,k+1){
ll c = 1;
while (i+c<=n){
if (dp[i+c][j+1] < dp[i][j] + (suff[i] - suff[i+c])*suff[i+c]){
ans[i+c][j+1] = i;
dp[i+c][j+1] = dp[i][j] + (suff[i] - suff[i+c])*suff[i+c];
}
c++;
}
dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
}
}
FOR(i,0,n+1){
FOR(j,0,k+1){
cout << dp[i][j] << " ";
}
cout << endl;
}
cout << dp[n][k] << endl;
ll sus = n;
FOR(i,0,k){
sus = ans[sus][k-i+1];
cout << sus << " ";
}
}
