#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define Youarestupid ios_base::sync_with_stdio(0);cin.tie(0);
#define all(x) x.begin() , x.end()
#define pofik continue
#define int long long
#define pb push_back
#define ins insert
#define sz size()
#define F first
#define S second
const int N = 1500 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-11;
using namespace std;
int T = 1 , sum;
int binpow(int a , int b){
if (!b) return 1;
if (b % 2){
return (a * binpow(a , b - 1)) % MOD;
}
else{
int val = binpow(a , b / 2);
return (val * val) % MOD;
}
}
int dp[N][N];
void solve(){
int n , k;
cin >> n >> k;
int a[n + 5];
int pref[n + 5] , suff[n + 5];
pref[0] = 0 , suff[n + 1] = 0;
for(int i = 1; i <= n; i++){ cin >> a[i]; pref[i] = pref[i - 1] + a[i]; }
for(int i = n; i >= 1; i--){ suff[i] = suff[i + 1] + a[i]; dp[i][1] = pref[i] * suff[i + 1]; }
for(int i = 1; i <= n; i++){
for(int l = 2; l <= n; l++){
dp[i][l] = inf;
for(int j = 1; j < i; j++){
dp[i][l] = max(dp[j][l - 1] + (pref[i] - pref[j]) * suff[i + 1] , dp[i][j]);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
ans = max(ans , dp[i][k]);
}
cout << ans;
}
signed main(){
Youarestupid
// cin >> T;
while(T--){
solve();
}
}
/*
___ __ _
| \ | | _____ | | _
| |\ \ | | __ __ | __ \ | | (_)
| | \ \ | | | | | || | \_\__ _| | _
| | \ \ | | | | | || | / _` | | | |
| | \ \| | | |__| || | / (_| | | | |
|_| \___| |______||_| \_,__|_| |_|
*/
