#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
int main() {
int n,splits;
cin >> n >> splits;
vector<vector<int>> dp(n, vector<int>(splits+2));
vector<vector<int>> pos(n, vector<int>(splits+2));
vector<int> xs(n);
vector<int> prefix(n);
for (int i = 0 ; i < n; ++i) {
cin >> xs[i];
prefix[i] = prefix[max(i-1,0)] + xs[i];
}
for (int i = 0; i < n-1; ++i) {
dp[i][1] = (prefix[n-1] - prefix[i]) * prefix[i];
}
for (int k = 2; k <= splits+1; ++k) {
for (int i = 0; i < n; ++ i) {
for (int l = 0; l < i; ++l) {
int v = dp[l][k-1] + (prefix[i] - prefix[l])*(prefix[n-1]-prefix[i]);
if (v >= dp[i][k]) {
dp[i][k] = v;
pos[i][k] = l;
}
}
}
}
cout << dp[n-1][splits+1] << '\n';
int i = n-1;
int k = splits+1;
vector<int> bt;
while(k > 1) {
bt.push_back(i);
i = pos[i][k];
k--;
}
//for (int j = bt.size()-1; j >= 0; --j) {
// cout << bt[j]-1 << ' ';
//}
cout << '\n';
}
